Longest Substring with At Most 2 Distinct

🎯

Longest Substring with At Most 2 Distinct

mediumHASH_MAPAmazonGoogle

Imagine you are analyzing a stream of characters from a user's typing pattern and want to find the longest segment where the user only used at most two different characters. This helps in understanding typing habits or detecting patterns.

💡 This problem is about finding a substring with constraints on the number of distinct characters. Beginners often struggle because they try to check all substrings naively, which is inefficient. Understanding how to track character frequencies and distinct counts efficiently is key.

📋

Problem Statement

Given a string s, find the length of the longest substring that contains at most two distinct characters. Input: A string s consisting of lowercase and/or uppercase English letters. Output: An integer representing the length of the longest substring with at most two distinct characters.

1 ≤ length of s ≤ 10^5s consists of English letters (both lowercase and uppercase)

💡

Example

Input"eceba"

Output3

The longest substring with at most 2 distinct characters is "ece" which has length 3.

Input"ccaabbb"

Output5

The longest substring with at most 2 distinct characters is "aabbb" which has length 5.

• Empty string → 0
• String with all identical characters → length of string
• String with all distinct characters → 2
• String with exactly two distinct characters → length of string

⚠️

Common Mistakes

Not updating the frequency map correctly when shrinking the window

Distinct count becomes incorrect, leading to wrong window size or infinite loop

✅ Always decrement frequency and remove character from map if frequency hits zero

Using nested loops without breaking early when distinct count exceeds 2

Unnecessary computations cause time limit exceeded errors

✅ Break inner loop immediately when distinct count exceeds 2 in brute force

Not handling empty string input

Code may crash or return incorrect result

✅ Check for empty input and return 0 immediately

Incorrectly calculating window size as right - left instead of right - left + 1

Returned length is off by one, causing wrong answers

✅ Use right - left + 1 to calculate window length correctly

Using a hash map without considering character set size leading to overhead

Slower performance than necessary

✅ Use fixed-size array for frequency if input is limited to ASCII

🧠

Brute Force (Nested Loops Checking All Substrings)

💡 This approach exists to build intuition by trying all possible substrings and checking their distinct character count. It is simple but inefficient, helping beginners understand the problem constraints and why optimization is needed.

Intuition

Try every possible substring and count how many distinct characters it contains. Keep track of the longest substring that has at most two distinct characters.

Algorithm

1. Initialize max_length to 0.
2. Use two nested loops to consider every substring s[i:j].
3. For each substring, count the distinct characters using a frequency map.
4. If the number of distinct characters is at most 2, update max_length if this substring is longer.

💡 The nested loops and counting distinct characters inside the inner loop make this approach slow and hard to optimize without better tracking.

</>

Code

def length_of_longest_substring_two_distinct(s: str) -> int:
    max_length = 0
    n = len(s)
    for i in range(n):
        freq = {}
        distinct_count = 0
        for j in range(i, n):
            freq[s[j]] = freq.get(s[j], 0) + 1
            if freq[s[j]] == 1:
                distinct_count += 1
            if distinct_count > 2:
                break
            max_length = max(max_length, j - i + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    test_str = "eceba"
    print(length_of_longest_substring_two_distinct(test_str))  # Expected output: 3

Line Notes

max_length = 0Initialize the variable to keep track of the longest valid substring found so far

for i in range(n)Outer loop picks the start index of the substring

freq = {}Reset frequency map for each new start index

for j in range(i, n)Inner loop extends the substring to the right

freq[s[j]] = freq.get(s[j], 0) + 1Update frequency count for the current character

if freq[s[j]] == 1If this character appears for the first time, increment distinct count

if distinct_count > 2If more than two distinct characters, stop expanding this substring

max_length = max(max_length, j - i + 1)Update max_length if current substring is longer

import java.util.*;

public class Solution {
    public static int lengthOfLongestSubstringTwoDistinct(String s) {
        int maxLength = 0;
        int n = s.length();
        for (int i = 0; i < n; i++) {
            Map<Character, Integer> freq = new HashMap<>();
            int distinctCount = 0;
            for (int j = i; j < n; j++) {
                char c = s.charAt(j);
                freq.put(c, freq.getOrDefault(c, 0) + 1);
                if (freq.get(c) == 1) {
                    distinctCount++;
                }
                if (distinctCount > 2) {
                    break;
                }
                maxLength = Math.max(maxLength, j - i + 1);
            }
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String testStr = "eceba";
        System.out.println(lengthOfLongestSubstringTwoDistinct(testStr)); // Expected output: 3
    }
}

Line Notes

int maxLength = 0;Initialize max length to track longest substring found

for (int i = 0; i < n; i++)Outer loop selects start index of substring

Map<Character, Integer> freq = new HashMap<>();Frequency map reset for each start index

for (int j = i; j < n; j++)Inner loop extends substring to the right

freq.put(c, freq.getOrDefault(c, 0) + 1);Update frequency count for current character

if (freq.get(c) == 1)Increment distinct count if character appears first time

if (distinctCount > 2)Stop if more than two distinct characters

maxLength = Math.max(maxLength, j - i + 1);Update max length if current substring is longer

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int lengthOfLongestSubstringTwoDistinct(string s) {
    int maxLength = 0;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        unordered_map<char, int> freq;
        int distinctCount = 0;
        for (int j = i; j < n; j++) {
            freq[s[j]]++;
            if (freq[s[j]] == 1) {
                distinctCount++;
            }
            if (distinctCount > 2) {
                break;
            }
            maxLength = max(maxLength, j - i + 1);
        }
    }
    return maxLength;
}

int main() {
    string testStr = "eceba";
    cout << lengthOfLongestSubstringTwoDistinct(testStr) << endl; // Expected output: 3
    return 0;
}

Line Notes

int maxLength = 0;Initialize max length to track longest substring found

for (int i = 0; i < n; i++)Outer loop selects start index of substring

unordered_map<char, int> freq;Frequency map reset for each start index

for (int j = i; j < n; j++)Inner loop extends substring to the right

freq[s[j]]++;Increment frequency count for current character

if (freq[s[j]] == 1)Increment distinct count if character appears first time

if (distinctCount > 2)Stop if more than two distinct characters

maxLength = max(maxLength, j - i + 1);Update max length if current substring is longer

function lengthOfLongestSubstringTwoDistinct(s) {
    let maxLength = 0;
    const n = s.length;
    for (let i = 0; i < n; i++) {
        const freq = new Map();
        let distinctCount = 0;
        for (let j = i; j < n; j++) {
            const c = s[j];
            freq.set(c, (freq.get(c) || 0) + 1);
            if (freq.get(c) === 1) {
                distinctCount++;
            }
            if (distinctCount > 2) {
                break;
            }
            maxLength = Math.max(maxLength, j - i + 1);
        }
    }
    return maxLength;
}

// Test
console.log(lengthOfLongestSubstringTwoDistinct("eceba")); // Expected output: 3

Line Notes

let maxLength = 0;Initialize max length to track longest substring found

for (let i = 0; i < n; i++)Outer loop selects start index of substring

const freq = new Map();Frequency map reset for each start index

for (let j = i; j < n; j++)Inner loop extends substring to the right

freq.set(c, (freq.get(c) || 0) + 1);Update frequency count for current character

if (freq.get(c) === 1)Increment distinct count if character appears first time

if (distinctCount > 2)Stop if more than two distinct characters

maxLength = Math.max(maxLength, j - i + 1);Update max length if current substring is longer

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Two nested loops generate O(n^2) substrings. Counting distinct characters inside inner loop can be O(n) in worst case, but here frequency map updates are O(1), so overall O(n^2).

💡 For n=20, this means about 400 substring checks, which is manageable, but for n=100000 it becomes 10 billion operations, which is too slow.

Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem and why optimization is needed.

🧠

Sliding Window with Frequency Map

💡 This approach improves efficiency by using a sliding window to track substrings and a frequency map to count characters, avoiding repeated work of checking all substrings.

Intuition

Expand the window to the right, adding characters and updating their counts. If the window has more than two distinct characters, shrink it from the left until it has at most two distinct characters again. Track the maximum window size during this process.

Algorithm

1. Initialize two pointers left and right at 0, and a frequency map.
2. Expand right pointer, adding characters to the frequency map.
3. If distinct characters exceed 2, move left pointer forward, decreasing frequencies until constraint is met.
4. Update max_length with the current window size whenever valid.

💡 The key is maintaining the window so that it always satisfies the constraint, which requires careful frequency tracking and pointer movement.

</>

Code

def length_of_longest_substring_two_distinct(s: str) -> int:
    freq = {}
    left = 0
    max_length = 0
    for right in range(len(s)):
        freq[s[right]] = freq.get(s[right], 0) + 1
        while len(freq) > 2:
            freq[s[left]] -= 1
            if freq[s[left]] == 0:
                del freq[s[left]]
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    test_str = "eceba"
    print(length_of_longest_substring_two_distinct(test_str))  # Expected output: 3

Line Notes

freq = {}Initialize frequency map to track characters in current window

left = 0Left pointer starts at beginning of string

for right in range(len(s))Right pointer expands window to the right

freq[s[right]] = freq.get(s[right], 0) + 1Add current character to frequency map

while len(freq) > 2If more than two distinct characters, shrink window from left

freq[s[left]] -= 1Decrease frequency of leftmost character

if freq[s[left]] == 0Remove character from map if frequency zero

left += 1Move left pointer forward to shrink window

max_length = max(max_length, right - left + 1)Update max length if current window is longer

import java.util.*;

public class Solution {
    public static int lengthOfLongestSubstringTwoDistinct(String s) {
        Map<Character, Integer> freq = new HashMap<>();
        int left = 0, maxLength = 0;
        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            freq.put(c, freq.getOrDefault(c, 0) + 1);
            while (freq.size() > 2) {
                char leftChar = s.charAt(left);
                freq.put(leftChar, freq.get(leftChar) - 1);
                if (freq.get(leftChar) == 0) {
                    freq.remove(leftChar);
                }
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String testStr = "eceba";
        System.out.println(lengthOfLongestSubstringTwoDistinct(testStr)); // Expected output: 3
    }
}

Line Notes

Map<Character, Integer> freq = new HashMap<>();Frequency map tracks characters in current window

int left = 0, maxLength = 0;Initialize left pointer and max length

for (int right = 0; right < s.length(); right++)Right pointer expands window

freq.put(c, freq.getOrDefault(c, 0) + 1);Add current character to frequency map

while (freq.size() > 2)Shrink window if more than two distinct characters

freq.put(leftChar, freq.get(leftChar) - 1);Decrease frequency of leftmost character

if (freq.get(leftChar) == 0)Remove character if frequency zero

left++;Move left pointer forward

maxLength = Math.max(maxLength, right - left + 1);Update max length if current window is longer

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int lengthOfLongestSubstringTwoDistinct(string s) {
    unordered_map<char, int> freq;
    int left = 0, maxLength = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        freq[s[right]]++;
        while ((int)freq.size() > 2) {
            freq[s[left]]--;
            if (freq[s[left]] == 0) {
                freq.erase(s[left]);
            }
            left++;
        }
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    string testStr = "eceba";
    cout << lengthOfLongestSubstringTwoDistinct(testStr) << endl; // Expected output: 3
    return 0;
}

Line Notes

unordered_map<char, int> freq;Frequency map tracks characters in current window

int left = 0, maxLength = 0;Initialize left pointer and max length

for (int right = 0; right < (int)s.size(); right++)Right pointer expands window

freq[s[right]]++;Add current character to frequency map

while ((int)freq.size() > 2)Shrink window if more than two distinct characters

freq[s[left]]--;Decrease frequency of leftmost character

if (freq[s[left]] == 0)Remove character if frequency zero

left++;Move left pointer forward

maxLength = max(maxLength, right - left + 1);Update max length if current window is longer

function lengthOfLongestSubstringTwoDistinct(s) {
    const freq = new Map();
    let left = 0, maxLength = 0;
    for (let right = 0; right < s.length; right++) {
        const c = s[right];
        freq.set(c, (freq.get(c) || 0) + 1);
        while (freq.size > 2) {
            const leftChar = s[left];
            freq.set(leftChar, freq.get(leftChar) - 1);
            if (freq.get(leftChar) === 0) {
                freq.delete(leftChar);
            }
            left++;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

// Test
console.log(lengthOfLongestSubstringTwoDistinct("eceba")); // Expected output: 3

Line Notes

const freq = new Map();Frequency map tracks characters in current window

let left = 0, maxLength = 0;Initialize left pointer and max length

for (let right = 0; right < s.length; right++)Right pointer expands window

freq.set(c, (freq.get(c) || 0) + 1);Add current character to frequency map

while (freq.size > 2)Shrink window if more than two distinct characters

freq.set(leftChar, freq.get(leftChar) - 1);Decrease frequency of leftmost character

if (freq.get(leftChar) === 0)Remove character if frequency zero

left++;Move left pointer forward

maxLength = Math.max(maxLength, right - left + 1);Update max length if current window is longer

⏱

Complexity

TimeO(n)

SpaceO(1)

Each character is visited at most twice by left and right pointers. Frequency map size is at most 3 during shrinking, so operations are O(1).

💡 For n=100000, this means roughly 200000 operations, which is efficient and suitable for large inputs.

Interview Verdict: Accepted / Optimal

This is the standard efficient solution that passes all tests and is expected in interviews.

🧠

Sliding Window with Fixed-Size Array for Frequencies (Optimization)

💡 This approach is a minor optimization of the sliding window by using a fixed-size array for character frequencies instead of a hash map, improving constant factors when input is limited to ASCII letters.

Intuition

Since input characters are English letters, use an array indexed by character code to track frequencies, which is faster than a hash map.

Algorithm

1. Initialize frequency array of size 128 (ASCII) to zero.
2. Use two pointers left and right to define the sliding window.
3. Expand right pointer, increment frequency of current character.
4. If distinct count exceeds 2, move left pointer forward, decrementing frequencies until constraint is met.
5. Update max_length with current window size.

💡 The logic is the same as the previous approach but uses an array for frequency tracking to reduce overhead.

</>

Code

def length_of_longest_substring_two_distinct(s: str) -> int:
    freq = [0] * 128
    left = 0
    max_length = 0
    distinct_count = 0
    for right in range(len(s)):
        if freq[ord(s[right])] == 0:
            distinct_count += 1
        freq[ord(s[right])] += 1
        while distinct_count > 2:
            freq[ord(s[left])] -= 1
            if freq[ord(s[left])] == 0:
                distinct_count -= 1
            left += 1
        max_length = max(max_length, right - left + 1)
    return max_length

# Driver code
if __name__ == '__main__':
    test_str = "eceba"
    print(length_of_longest_substring_two_distinct(test_str))  # Expected output: 3

Line Notes

freq = [0] * 128Initialize fixed-size frequency array for ASCII characters

distinct_count = 0Track number of distinct characters in current window

if freq[ord(s[right])] == 0If character not seen before in window, increment distinct count

freq[ord(s[right])] += 1Increment frequency of current character

while distinct_count > 2Shrink window if more than two distinct characters

freq[ord(s[left])] -= 1Decrement frequency of leftmost character

if freq[ord(s[left])] == 0If frequency zero, decrement distinct count

left += 1Move left pointer forward

max_length = max(max_length, right - left + 1)Update max length if current window is longer

public class Solution {
    public static int lengthOfLongestSubstringTwoDistinct(String s) {
        int[] freq = new int[128];
        int left = 0, maxLength = 0, distinctCount = 0;
        for (int right = 0; right < s.length(); right++) {
            if (freq[s.charAt(right)] == 0) {
                distinctCount++;
            }
            freq[s.charAt(right)]++;
            while (distinctCount > 2) {
                freq[s.charAt(left)]--;
                if (freq[s.charAt(left)] == 0) {
                    distinctCount--;
                }
                left++;
            }
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }

    public static void main(String[] args) {
        String testStr = "eceba";
        System.out.println(lengthOfLongestSubstringTwoDistinct(testStr)); // Expected output: 3
    }
}

Line Notes

int[] freq = new int[128];Fixed-size frequency array for ASCII characters

int left = 0, maxLength = 0, distinctCount = 0;Initialize pointers and distinct count

if (freq[s.charAt(right)] == 0)If character not seen before, increment distinct count

freq[s.charAt(right)]++;Increment frequency of current character

while (distinctCount > 2)Shrink window if more than two distinct characters

freq[s.charAt(left)]--;Decrement frequency of leftmost character

if (freq[s.charAt(left)] == 0)Decrement distinct count if frequency zero

left++;Move left pointer forward

maxLength = Math.max(maxLength, right - left + 1);Update max length if current window is longer

#include <iostream>
#include <string>
using namespace std;

int lengthOfLongestSubstringTwoDistinct(string s) {
    int freq[128] = {0};
    int left = 0, maxLength = 0, distinctCount = 0;
    for (int right = 0; right < (int)s.size(); right++) {
        if (freq[s[right]] == 0) {
            distinctCount++;
        }
        freq[s[right]]++;
        while (distinctCount > 2) {
            freq[s[left]]--;
            if (freq[s[left]] == 0) {
                distinctCount--;
            }
            left++;
        }
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    string testStr = "eceba";
    cout << lengthOfLongestSubstringTwoDistinct(testStr) << endl; // Expected output: 3
    return 0;
}

Line Notes

int freq[128] = {0};Fixed-size frequency array for ASCII characters

int left = 0, maxLength = 0, distinctCount = 0;Initialize pointers and distinct count

if (freq[s[right]] == 0)If character not seen before, increment distinct count

freq[s[right]]++;Increment frequency of current character

while (distinctCount > 2)Shrink window if more than two distinct characters

freq[s[left]]--;Decrement frequency of leftmost character

if (freq[s[left]] == 0)Decrement distinct count if frequency zero

left++;Move left pointer forward

maxLength = max(maxLength, right - left + 1);Update max length if current window is longer

function lengthOfLongestSubstringTwoDistinct(s) {
    const freq = new Array(128).fill(0);
    let left = 0, maxLength = 0, distinctCount = 0;
    for (let right = 0; right < s.length; right++) {
        if (freq[s.charCodeAt(right)] === 0) {
            distinctCount++;
        }
        freq[s.charCodeAt(right)]++;
        while (distinctCount > 2) {
            freq[s.charCodeAt(left)]--;
            if (freq[s.charCodeAt(left)] === 0) {
                distinctCount--;
            }
            left++;
        }
        maxLength = Math.max(maxLength, right - left + 1);
    }
    return maxLength;
}

// Test
console.log(lengthOfLongestSubstringTwoDistinct("eceba")); // Expected output: 3

Line Notes

const freq = new Array(128).fill(0);Fixed-size frequency array for ASCII characters

let left = 0, maxLength = 0, distinctCount = 0;Initialize pointers and distinct count

if (freq[s.charCodeAt(right)] === 0)If character not seen before, increment distinct count

freq[s.charCodeAt(right)]++;Increment frequency of current character

while (distinctCount > 2)Shrink window if more than two distinct characters

freq[s.charCodeAt(left)]--;Decrement frequency of leftmost character

if (freq[s.charCodeAt(left)] === 0)Decrement distinct count if frequency zero

left++;Move left pointer forward

maxLength = Math.max(maxLength, right - left + 1);Update max length if current window is longer

⏱

Complexity

TimeO(n)

SpaceO(1)

Same linear time complexity as previous approach, but constant space is fixed and operations are faster due to array indexing.

💡 This approach is a micro-optimization useful when input is limited to ASCII characters.

Interview Verdict: Accepted / Optimal with minor optimization

This is a practical optimization that can be mentioned or coded if time permits.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the sliding window with frequency map (Approach 2) is the best to code. Brute force is only for explanation, and fixed array optimization is optional.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code
2. Sliding Window with Hash Map	O(n)	O(1)	No	Yes	Code this approach
3. Sliding Window with Fixed Array	O(n)	O(1)	No	Yes	Mention or code if time permits

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding, followed by the sliding window solution for efficiency. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce the sliding window technique with a frequency map.Step 4: Code the sliding window solution carefully.Step 5: Test with sample and edge cases.Step 6: Discuss possible optimizations if time permits.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to identify the sliding window pattern, correctly track frequencies and distinct counts, and write clean, bug-free code that handles edge cases.

Common Follow-ups

• What if the problem changes to at most K distinct characters? → Generalize sliding window with K.
• How to return the substring itself, not just length? → Track start index of max window.

💡 These follow-ups test your ability to generalize the solution and handle variations.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest/shortest substring or subarray. 2) Constraint on number of distinct elements. 3) Need to track frequencies or counts. 4) Sliding window or two-pointer technique is applicable.

Signature Phrases

"longest substring with at most 2 distinct characters""find substring with limited distinct elements"

NOT This Pattern When

Problems asking for substrings with exact distinct counts or other constraints like palindromes require different approaches.

Similar Problems

Longest Substring Without Repeating Characters - similar sliding window techniqueLongest Substring with At Most K Distinct Characters - generalization of this problem

Practice

1. You are given two strings s and t. The task is to find the smallest substring in s that contains all characters of t including duplicates. Which algorithmic approach guarantees an optimal solution in terms of time complexity?

easy

A. Sliding window with two pointers and frequency maps to track required characters

B. Brute force checking of all substrings and verifying character counts

C. Dynamic programming to build solutions for all substrings

D. Greedy approach expanding window until all characters are found, then stopping

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the minimum window substring containing all characters of t, including duplicates, which suggests tracking frequencies.

2. Step 2: Identify suitable algorithm

   Brute force is correct but inefficient (O(n^3)). DP is not suitable as substring problems with character counts are not naturally solved by DP. Greedy stopping early can miss smaller windows. Sliding window with frequency maps efficiently tracks counts and adjusts window size, guaranteeing optimal O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window with frequency maps is the classic optimal approach [OK]

Hint: Sliding window tracks frequencies optimally [OK]

Common Mistakes:

• Assuming greedy expansion alone suffices
• Thinking DP solves substring frequency problems efficiently

2. You are given an integer array and two bounds left and right. You need to count the number of contiguous subarrays where the maximum element lies between left and right inclusive. Which approach guarantees an optimal solution with linear time complexity?

easy

A. Sort the array and use binary search to find valid subarrays within bounds.

B. Use a brute force nested loop to check every subarray and track its maximum.

C. Use a sliding window that expands and contracts based on the current maximum element.

D. Count subarrays with max ≤ right and subtract those with max < left using a single pass.

Solution

1. Step 1: Understand the problem constraints

   The problem requires counting subarrays with maximum elements bounded between left and right, which can be done efficiently by counting subarrays with max ≤ right and subtracting those with max < left.

2. Step 2: Identify the optimal approach

   The approach that counts subarrays with max ≤ right and subtracts those with max < left uses a single linear pass and constant space, guaranteeing O(n) time complexity.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Optimal linear approach uses subtraction of two counts [OK]

Hint: Subtract counts of subarrays bounded by right and left-1 [OK]

Common Mistakes:

• Assuming sliding window can track max efficiently
• Trying to sort and binary search subarrays
• Using brute force for optimal solution

3. Consider the following code snippet for finding the longest subarray with equal number of 0s and 1s. What is the value of max_length after processing the input [0, 1, 0, 1]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace prefix sums and first_occurrence updates.

   For input [0,1,0,1], prefix sums are: -1, 0, -1, 0 with offset indexing.

2. Step 2: Update max_length when prefix sum repeats.

   At i=1, prefix_sum=0 repeats at index -1 -> length=2; at i=3, prefix_sum=0 repeats again -> length=4.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Longest balanced subarray is entire array length 4 [OK]

Hint: Prefix sum repeats indicate balanced subarray [OK]

Common Mistakes:

• Off-by-one in length calculation
• Confusing prefix sum indexing
• Ignoring initial prefix sum at -1

4. The following code attempts to solve the Continuous Subarray Sum problem. Identify the line containing the subtle bug that causes incorrect results on some inputs.

medium

A. Line 7: updating remainder_map[running_sum] = i before checking condition

B. Line 11: verifying subarray length > 1

C. Line 9: checking if running_sum in remainder_map

D. Line 3: initializing running_sum to 0

Solution

1. Step 1: Understand remainder_map update timing

   The original code updated remainder_map[running_sum] = i before checking if running_sum already exists, overwriting the earliest index.

2. Step 2: Identify consequence of overwriting

   Overwriting earliest index causes missing longer subarrays that satisfy the condition, leading to false negatives.

3. Step 3: Correct the code

   Update remainder_map[running_sum] = i only if running_sum is not already in remainder_map, preserving earliest occurrence.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Correct code inserts remainder only if not present to preserve earliest index [OK]

Hint: Earliest remainder index must be preserved to find valid subarrays [OK]

Common Mistakes:

• Updating remainder map on every occurrence
• Not checking subarray length >= 2
• Modulo by zero errors

5. Suppose the array can contain negative numbers and you want to find all pivot indices (not just the first). Which modification to the optimal single-pass algorithm correctly finds all pivot indices?

hard

A. Run the single-pass algorithm once and return the first pivot index found.

B. Modify the single-pass algorithm to collect all indices where left_sum == total - left_sum - num instead of returning immediately.

C. Use prefix sums to precompute sums and then check each index in a separate loop.

D. Sort the array and use two pointers to find all pivot indices efficiently.

Solution

1. Step 1: Understand the requirement

   We need all pivot indices, not just the first.

2. Step 2: Modify the single-pass approach

   Instead of returning immediately when a pivot is found, collect the index and continue iterating.

3. Step 3: Avoid sorting or extra loops

   Sorting breaks the order and two loops increase complexity unnecessarily.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Collecting all valid indices in one pass is efficient and correct [OK]

Hint: Collect all pivots during single pass instead of early return [OK]

Common Mistakes:

• Returning early and missing other pivots
• Using sorting which breaks index order
• Using nested loops increasing complexity