Longest Common Prefix in DSA Javascript - Time & Space Complexity

Time Complexity: Longest Common Prefix

O(n * m)

Understanding Time Complexity

We want to understand how the time needed to find the longest common prefix grows as we add more words or longer words.

How does the work increase when the input list or word length grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.slice(0, prefix.length - 1);
      if (prefix === "") return "";
    }
  }
  return prefix;
}
    

This code finds the longest common prefix string among an array of strings by comparing prefixes and shortening them until all strings match.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The outer loop goes through each string, and the inner while loop shortens the prefix until it matches the start of the current string.
• How many times: The outer loop runs once per string (n times), and the inner loop can run up to the length of the prefix (m times) in the worst case.

How Execution Grows With Input

As the number of strings (n) or the length of the prefix (m) grows, the operations increase roughly by multiplying these two factors.

Input Size (n)	Approx. Operations
10 strings, prefix length 5	About 50 checks
100 strings, prefix length 10	About 1000 checks
1000 strings, prefix length 20	About 20,000 checks

Pattern observation: The work grows roughly by multiplying the number of strings by the prefix length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time grows proportionally to the number of strings times the length of the prefix we check.

Common Mistake

[X] Wrong: "The time depends only on the number of strings, not their length."

[OK] Correct: The prefix length matters because we compare characters one by one, so longer prefixes mean more work per string.

Interview Connect

Understanding this time complexity helps you explain how your solution scales and shows you can analyze nested loops clearly.

Self-Check

"What if we sorted the strings first and only compared the first and last strings? How would the time complexity change?"

Practice

1. What does the Longest Common Prefix (LCP) problem ask you to find given an array of strings?

easy

A. The longest substring common to any two strings

B. The longest starting substring common to all strings

C. The longest ending substring common to all strings

D. The shortest substring unique to each string

Solution

1. Step 1: Understand the problem definition

   The Longest Common Prefix means the longest substring at the start of all strings that is the same.

2. Step 2: Compare options with definition

   Only The longest starting substring common to all strings matches this definition exactly.

3. Final Answer:

   The longest starting substring common to all strings -> Option B

4. Quick Check:

   Longest Common Prefix = longest starting substring [OK]

Hint: Focus on the start of strings for common prefix [OK]

Common Mistakes:

• Confusing prefix with suffix
• Looking for substring anywhere, not just start
• Thinking about unique substrings

2. Which of the following is the correct JavaScript syntax to start a function named longestCommonPrefix that takes an array strs as input?

easy

A. function: longestCommonPrefix(strs) { }

B. func longestCommonPrefix(strs) { }

C. function longestCommonPrefix(strs) { }

D. def longestCommonPrefix(strs):

Solution

1. Step 1: Recall JavaScript function syntax

   JavaScript functions start with the keyword 'function' followed by name and parentheses.

2. Step 2: Check each option

   function longestCommonPrefix(strs) { } matches JavaScript syntax. Options B and C are from other languages. function: longestCommonPrefix(strs) { } is invalid syntax.

3. Final Answer:

   function longestCommonPrefix(strs) { } -> Option C

4. Quick Check:

   JS function syntax = function name(params) { } [OK]

Hint: JS functions start with 'function' keyword [OK]

Common Mistakes:

• Using Python or other language syntax
• Adding colon after function name
• Using 'func' instead of 'function'

3. What will be the output of the following JavaScript code?

function longestCommonPrefix(strs) {
  if (strs.length === 0) return "";
  let prefix = strs[0];
  for (let i = 1; i < strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (prefix === "") return "";
    }
  }
  return prefix;
}

console.log(longestCommonPrefix(["flower", "flow", "flight"]));

medium

A. "fl"

B. "flow"

C. "f"

D. "flower"

Solution

1. Step 1: Initialize prefix and loop through strings

   Prefix starts as "flower". Check "flow": "flower" is not prefix, shorten to "flowe", then "flow", which matches start of "flow".

2. Step 2: Check next string "flight"

   "flow" is not prefix of "flight", shorten to "flo", no match; then "fl", which matches start of "flight".

3. Final Answer:

   "fl" -> Option A

4. Quick Check:

   Common prefix of flower, flow, flight = "fl" [OK]

Hint: Shrink prefix until it matches all strings start [OK]

Common Mistakes:

• Returning first string as prefix
• Not shrinking prefix correctly
• Confusing substring with suffix

4. Find the bug in this JavaScript function for Longest Common Prefix:

function longestCommonPrefix(strs) {
  if (!strs.length) return "";
  let prefix = strs[0];
  for (let i = 1; i <= strs.length; i++) {
    while (strs[i].indexOf(prefix) !== 0) {
      prefix = prefix.substring(0, prefix.length - 1);
      if (prefix === "") return "";
    }
  }
  return prefix;
}

medium

A. The for loop condition should be i < strs.length, not i <= strs.length

B. The prefix should be initialized as an empty string

C. The while loop condition should use includes() instead of indexOf()

D. The function should return prefix inside the for loop

Solution

1. Step 1: Check for loop bounds

   The for loop uses i <= strs.length, which causes out-of-bounds access at last iteration.

2. Step 2: Correct loop condition

   Changing to i < strs.length prevents accessing undefined strs[i].

3. Final Answer:

   The for loop condition should be i < strs.length, not i <= strs.length -> Option A

4. Quick Check:

   Loop index must be less than array length [OK]

Hint: Use < not <= for array indices [OK]

Common Mistakes:

• Off-by-one error in loop
• Wrong initialization of prefix
• Misusing string methods

5. Given an array of strings, how would you modify the Longest Common Prefix algorithm to handle the case where some strings are empty or the array is empty, ensuring no errors and correct output?

hard

A. Throw an error if any string is empty

B. Ignore empty strings and find prefix among non-empty strings only

C. Replace empty strings with the first string in the array before processing

D. Return an empty string immediately if the array is empty or any string is empty

Solution

1. Step 1: Check for empty array or empty strings

   If the array is empty or any string is empty, the longest common prefix must be empty string.

2. Step 2: Return empty string early

   Returning "" immediately avoids errors and matches expected output.

3. Final Answer:

   Return an empty string immediately if the array is empty or any string is empty -> Option D

4. Quick Check:

   Empty input means empty prefix [OK]

Hint: Check for empty inputs first [OK]

Common Mistakes:

• Not handling empty strings causing errors
• Ignoring empty strings and causing wrong prefix
• Throwing errors instead of returning empty string