Longest Common Prefix in DSA Javascript - Execution Trace

Concept Flow - Longest Common Prefix

Start with first string as prefix

↓

Compare prefix with next string

↓

Find common prefix between prefix and current string

↓

Update prefix

↓

More strings?

Yes→Repeat comparison

No↓

Return prefix

Start with the first string as the prefix. Compare it with each string to find the common prefix. Update the prefix each time. Stop when no more strings or prefix is empty.

Execution Sample

DSA Javascript

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.slice(0, prefix.length - 1);
      if (prefix === "") return "";
    }
  }
  return prefix;
}

Finds the longest common prefix string among an array of strings by shrinking the prefix until it matches all strings.

Execution Table

Step	Operation	Current String	Prefix Before	Prefix After	Visual State
1	Initialize prefix	N/A	N/A	flower	[flower]
2	Compare with 'flow'	flow	flower	flow	[flow]
3	Compare with 'flight'	flight	flow	fl	[fl]
4	No more strings	N/A	fl	fl	[fl]

💡 All strings processed or prefix reduced to empty

Variable Tracker

Variable	Start	After 1	After 2	Final
prefix	N/A	flower	flow	fl
i	N/A	1	2	3

Key Moments - 3 Insights

Why do we reduce the prefix inside a while loop?

Because the prefix must match the start of the current string. If it doesn't, we remove the last character until it matches or becomes empty. See execution_table step 2 and 3.

What happens if the input array is empty?

The function returns an empty string immediately, as shown in the code's first line and no steps in execution_table.

Why do we start prefix as the first string?

Because the longest common prefix cannot be longer than any string. Starting with the first string lets us shrink it as needed. See execution_table step 1.

Visual Quiz - 3 Questions

Look at the execution_table, what is the prefix after comparing with the second string?

A flow

B flower

C fl

D flight

💡 Hint

Check execution_table row 2 under 'Prefix After'

At which step does the prefix become 'fl'?

A Step 2

B Step 3

C Step 1

D Step 4

💡 Hint

Look at execution_table row 3 under 'Prefix After'

If the input array was empty, what would the prefix be?

A flower

B fl

C "" (empty string)

D undefined

💡 Hint

Refer to the code's first line and key_moments about empty input

Concept Snapshot

Longest Common Prefix:
- Start prefix as first string
- Compare prefix with each string
- Shrink prefix until it matches start
- Stop when no more strings or prefix empty
- Return prefix as result

Full Transcript

This concept finds the longest common prefix among strings. We start with the first string as the prefix. Then, for each next string, we check if it starts with the prefix. If not, we remove the last character from the prefix until it matches or becomes empty. We repeat this for all strings. If the input is empty, we return an empty string. The final prefix is the longest common prefix shared by all strings.

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