Backspace String Compare

🎯

Backspace String Compare

easyTWO_POINTERAmazonFacebookGoogle

Imagine typing a message on your phone where you often hit backspace. How can you verify if two typed messages are actually the same after considering all backspaces?

💡 This problem involves simulating the effect of backspace characters in strings. Beginners often struggle because they try to process the strings directly without simulating the backspaces properly, leading to incorrect comparisons.

📋

Problem Statement

Given two strings S and T, return true if they are equal when both are typed into empty text editors. '#' means a backspace character. If a backspace is encountered, it deletes the character before it if any. Return true if the final strings are equal, otherwise false.

1 ≤ length of S, T ≤ 10^5S and T consist of lowercase letters and '#' characters only

💡

Example

Input"S = \"ab#c\", T = \"ad#c\""

Outputtrue

Both become "ac" after processing backspaces.

Input"S = \"ab##\", T = \"c#d#\""

Outputtrue

Both become "" (empty string) after processing.

Input"S = \"a#c\", T = \"b\""

Outputfalse

S becomes "c" but T is "b".

• Both strings empty → true
• Strings with only backspaces → true
• One string empty, other non-empty → false
• Backspaces at the start of the string → handled correctly

⚠️

Common Mistakes

Not handling backspaces at the start of the string

Index errors or incorrect final string

✅ Check if stack or pointer is empty before popping/skipping

Comparing strings before fully processing backspaces

False negatives because strings appear different

✅ Always process entire strings before comparison

Using extra space unnecessarily in two-pointer approach

Higher memory usage than needed

✅ Use pointers from the end and skip counters to avoid extra stacks

Off-by-one errors when moving pointers

Incorrect character comparisons or infinite loops

✅ Carefully decrement pointers after processing each character

Not testing empty strings or strings with only backspaces

Missed edge cases cause wrong answers

✅ Include edge cases in testing

🧠

Brute Force (Build Final Strings Using Stack)

💡 This approach exists to help beginners understand the problem by simulating the backspace effect explicitly. It is intuitive but not the most optimal in terms of space.

Intuition

Simulate typing each string into a text editor by using a stack to process characters and backspaces, then compare the resulting strings.

Algorithm

1. Initialize two empty stacks for S and T.
2. Iterate over each character in S: push if letter, pop if '#'.
3. Repeat for T similarly.
4. Compare the two stacks converted back to strings for equality.

💡 The main challenge is to simulate backspaces correctly; stacks provide a direct way to do this.

</>

Code

def backspaceCompare(S: str, T: str) -> bool:
    def build(string):
        stack = []
        for ch in string:
            if ch != '#':
                stack.append(ch)
            elif stack:
                stack.pop()
        return ''.join(stack)

    return build(S) == build(T)

# Driver code
if __name__ == '__main__':
    print(backspaceCompare("ab#c", "ad#c"))  # True
    print(backspaceCompare("ab##", "c#d#"))  # True
    print(backspaceCompare("a#c", "b"))      # False

Line Notes

def build(string):Helper function to simulate typing with backspaces

stack = []Initialize stack to store characters typed

if ch != '#':If current char is normal, add to stack

elif stack:If backspace and stack not empty, remove last char

return ''.join(stack)Return the final string after processing

return build(S) == build(T)Compare processed strings for equality

import java.util.*;

public class Solution {
    public static boolean backspaceCompare(String S, String T) {
        return build(S).equals(build(T));
    }

    private static String build(String str) {
        Stack<Character> stack = new Stack<>();
        for (char ch : str.toCharArray()) {
            if (ch != '#') {
                stack.push(ch);
            } else if (!stack.isEmpty()) {
                stack.pop();
            }
        }
        StringBuilder sb = new StringBuilder();
        for (char c : stack) sb.append(c);
        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println(backspaceCompare("ab#c", "ad#c")); // true
        System.out.println(backspaceCompare("ab##", "c#d#")); // true
        System.out.println(backspaceCompare("a#c", "b"));     // false
    }
}

Line Notes

public static boolean backspaceCompare(String S, String T)Main function comparing processed strings

return build(S).equals(build(T));Compare final strings after backspace processing

Stack<Character> stack = new Stack<>();Stack to simulate typing

if (ch != '#')Add character if not backspace

else if (!stack.isEmpty())Pop last character if backspace and stack not empty

StringBuilder sb = new StringBuilder();Build final string from stack

#include <iostream>
#include <stack>
#include <string>

using namespace std;

string build(const string& str) {
    stack<char> st;
    for (char ch : str) {
        if (ch != '#') {
            st.push(ch);
        } else if (!st.empty()) {
            st.pop();
        }
    }
    string result;
    while (!st.empty()) {
        result += st.top();
        st.pop();
    }
    reverse(result.begin(), result.end());
    return result;
}

bool backspaceCompare(string S, string T) {
    return build(S) == build(T);
}

int main() {
    cout << boolalpha;
    cout << backspaceCompare("ab#c", "ad#c") << '\n'; // true
    cout << backspaceCompare("ab##", "c#d#") << '\n'; // true
    cout << backspaceCompare("a#c", "b") << '\n';     // false
    return 0;
}

Line Notes

string build(const string& str)Helper to simulate typing with backspaces

stack<char> st;Stack to hold characters typed

if (ch != '#')Push character if not backspace

else if (!st.empty())Pop last character if backspace and stack not empty

reverse(result.begin(), result.end());Reverse because stack pops in reverse order

return build(S) == build(T);Compare final processed strings

function backspaceCompare(S, T) {
    function build(str) {
        const stack = [];
        for (const ch of str) {
            if (ch !== '#') {
                stack.push(ch);
            } else if (stack.length > 0) {
                stack.pop();
            }
        }
        return stack.join('');
    }
    return build(S) === build(T);
}

// Test cases
console.log(backspaceCompare("ab#c", "ad#c")); // true
console.log(backspaceCompare("ab##", "c#d#")); // true
console.log(backspaceCompare("a#c", "b"));     // false

Line Notes

function build(str)Helper function to simulate typing

const stack = []Stack to hold characters typed

if (ch !== '#')Push character if not backspace

else if (stack.length > 0)Pop last character if backspace and stack not empty

return stack.join('')Return final string after processing

return build(S) === build(T)Compare processed strings for equality

⏱

Complexity

TimeO(n + m)

SpaceO(n + m)

We process each character once for both strings, and use stacks that can grow up to the length of the strings.

💡 For strings of length 100,000, this means about 200,000 operations and memory proportional to input size.

Interview Verdict: Accepted

This approach works well but uses extra space; it's a good starting point to understand the problem.

🧠

Two Pointers from End (Simulate Backspaces On The Fly)

💡 This approach improves space by simulating the backspace effect while traversing from the end, avoiding extra stacks.

Intuition

Start from the end of both strings and move backwards, skipping characters that should be deleted due to backspaces, then compare characters one by one.

Algorithm

1. Initialize two pointers at the end of S and T.
2. For each pointer, skip characters that are deleted by backspaces using a skip counter.
3. Compare the current characters after skipping; if different, return false.
4. Move both pointers backward and repeat until both strings are fully traversed.

💡 The tricky part is correctly skipping characters affected by backspaces before comparing.

</>

Code

def backspaceCompare(S: str, T: str) -> bool:
    i, j = len(S) - 1, len(T) - 1
    skipS = skipT = 0

    while i >= 0 or j >= 0:
        while i >= 0:
            if S[i] == '#':
                skipS += 1
                i -= 1
            elif skipS > 0:
                skipS -= 1
                i -= 1
            else:
                break
        while j >= 0:
            if T[j] == '#':
                skipT += 1
                j -= 1
            elif skipT > 0:
                skipT -= 1
                j -= 1
            else:
                break
        if i >= 0 and j >= 0 and S[i] != T[j]:
            return False
        if (i >= 0) != (j >= 0):
            return False
        i -= 1
        j -= 1
    return True

# Driver code
if __name__ == '__main__':
    print(backspaceCompare("ab#c", "ad#c"))  # True
    print(backspaceCompare("ab##", "c#d#"))  # True
    print(backspaceCompare("a#c", "b"))      # False

Line Notes

i, j = len(S) - 1, len(T) - 1Start pointers at the end of each string

skipS = skipT = 0Counters to track how many chars to skip due to backspaces

while i >= 0:Skip characters in S affected by backspaces

if S[i] == '#':Increment skip counter when backspace found

elif skipS > 0:Skip a character if skip counter positive

if i >= 0 and j >= 0 and S[i] != T[j]:Compare current characters after skipping

if (i >= 0) != (j >= 0):If one string ended before the other, return false

i -= 1; j -= 1Move both pointers backward

public class Solution {
    public static boolean backspaceCompare(String S, String T) {
        int i = S.length() - 1, j = T.length() - 1;
        int skipS = 0, skipT = 0;

        while (i >= 0 || j >= 0) {
            while (i >= 0) {
                if (S.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j)) return false;
            if ((i >= 0) != (j >= 0)) return false;
            i--;
            j--;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(backspaceCompare("ab#c", "ad#c")); // true
        System.out.println(backspaceCompare("ab##", "c#d#")); // true
        System.out.println(backspaceCompare("a#c", "b"));     // false
    }
}

Line Notes

int i = S.length() - 1, j = T.length() - 1;Initialize pointers at end of strings

int skipS = 0, skipT = 0;Skip counters for backspaces

while (i >= 0)Skip characters in S affected by backspaces

if (S.charAt(i) == '#')Increment skip counter on backspace

else if (skipS > 0)Skip character if skip counter positive

if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))Compare current characters

if ((i >= 0) != (j >= 0))Check if one string ended before the other

i--; j--;Move pointers backward

#include <iostream>
#include <string>

using namespace std;

bool backspaceCompare(string S, string T) {
    int i = (int)S.size() - 1, j = (int)T.size() - 1;
    int skipS = 0, skipT = 0;

    while (i >= 0 || j >= 0) {
        while (i >= 0) {
            if (S[i] == '#') {
                skipS++;
                i--;
            } else if (skipS > 0) {
                skipS--;
                i--;
            } else {
                break;
            }
        }
        while (j >= 0) {
            if (T[j] == '#') {
                skipT++;
                j--;
            } else if (skipT > 0) {
                skipT--;
                j--;
            } else {
                break;
            }
        }
        if (i >= 0 && j >= 0 && S[i] != T[j]) return false;
        if ((i >= 0) != (j >= 0)) return false;
        i--;
        j--;
    }
    return true;
}

int main() {
    cout << boolalpha;
    cout << backspaceCompare("ab#c", "ad#c") << '\n'; // true
    cout << backspaceCompare("ab##", "c#d#") << '\n'; // true
    cout << backspaceCompare("a#c", "b") << '\n';     // false
    return 0;
}

Line Notes

int i = (int)S.size() - 1, j = (int)T.size() - 1;Pointers start at end of strings

int skipS = 0, skipT = 0;Skip counters for backspaces

while (i >= 0)Skip characters in S affected by backspaces

if (S[i] == '#')Increment skip counter on backspace

else if (skipS > 0)Skip character if skip counter positive

if (i >= 0 && j >= 0 && S[i] != T[j])Compare current characters

if ((i >= 0) != (j >= 0))Check if one string ended before the other

i--; j--;Move pointers backward

function backspaceCompare(S, T) {
    let i = S.length - 1, j = T.length - 1;
    let skipS = 0, skipT = 0;

    while (i >= 0 || j >= 0) {
        while (i >= 0) {
            if (S[i] === '#') {
                skipS++;
                i--;
            } else if (skipS > 0) {
                skipS--;
                i--;
            } else {
                break;
            }
        }
        while (j >= 0) {
            if (T[j] === '#') {
                skipT++;
                j--;
            } else if (skipT > 0) {
                skipT--;
                j--;
            } else {
                break;
            }
        }
        if (i >= 0 && j >= 0 && S[i] !== T[j]) return false;
        if ((i >= 0) !== (j >= 0)) return false;
        i--;
        j--;
    }
    return true;
}

// Test cases
console.log(backspaceCompare("ab#c", "ad#c")); // true
console.log(backspaceCompare("ab##", "c#d#")); // true
console.log(backspaceCompare("a#c", "b"));     // false

Line Notes

let i = S.length - 1, j = T.length - 1;Initialize pointers at end

let skipS = 0, skipT = 0;Skip counters for backspaces

while (i >= 0)Skip characters in S affected by backspaces

if (S[i] === '#')Increment skip counter on backspace

else if (skipS > 0)Skip character if skip counter positive

if (i >= 0 && j >= 0 && S[i] !== T[j])Compare current characters

if ((i >= 0) !== (j >= 0))Check if one string ended before the other

i--; j--;Move pointers backward

⏱

Complexity

TimeO(n + m)

SpaceO(1)

Each character is processed at most once from the end, and no extra space proportional to input size is used.

💡 For strings of length 100,000, this means about 200,000 operations but constant extra memory.

Interview Verdict: Accepted

This is the preferred approach in interviews due to its optimal space usage and clear logic.

🧠

Rebuild Strings Using Two Pointers Forward (In-Place Simulation)

💡 This approach simulates the typing process in-place by overwriting characters in the original string arrays, saving space compared to stacks but requiring careful pointer management.

Intuition

Use two pointers to rebuild the final string by skipping backspaced characters as you iterate forward, then compare the rebuilt strings.

Algorithm

1. Convert strings to character arrays for mutability.
2. Use a write pointer to overwrite characters while iterating forward.
3. When a backspace is encountered, move the write pointer back if possible.
4. After processing, compare the rebuilt strings up to the write pointer.

💡 The challenge is managing the write pointer correctly to simulate backspaces without extra space.

</>

Code

def backspaceCompare(S: str, T: str) -> bool:
    def build(arr):
        write = 0
        for read in range(len(arr)):
            if arr[read] != '#':
                arr[write] = arr[read]
                write += 1
            elif write > 0:
                write -= 1
        return ''.join(arr[:write])

    return build(list(S)) == build(list(T))

# Driver code
if __name__ == '__main__':
    print(backspaceCompare("ab#c", "ad#c"))  # True
    print(backspaceCompare("ab##", "c#d#"))  # True
    print(backspaceCompare("a#c", "b"))      # False

Line Notes

def build(arr):Helper to rebuild string simulating backspaces in-place

write = 0Write pointer to track position to overwrite

if arr[read] != '#':Copy character if not backspace

elif write > 0:Move write pointer back to simulate backspace

return ''.join(arr[:write])Return rebuilt string up to write pointer

return build(list(S)) == build(list(T))Compare rebuilt strings

public class Solution {
    public static boolean backspaceCompare(String S, String T) {
        return build(S.toCharArray()).equals(build(T.toCharArray()));
    }

    private static String build(char[] arr) {
        int write = 0;
        for (int read = 0; read < arr.length; read++) {
            if (arr[read] != '#') {
                arr[write++] = arr[read];
            } else if (write > 0) {
                write--;
            }
        }
        return new String(arr, 0, write);
    }

    public static void main(String[] args) {
        System.out.println(backspaceCompare("ab#c", "ad#c")); // true
        System.out.println(backspaceCompare("ab##", "c#d#")); // true
        System.out.println(backspaceCompare("a#c", "b"));     // false
    }
}

Line Notes

return build(S.toCharArray()).equals(build(T.toCharArray()));Convert strings to char arrays and compare rebuilt strings

int write = 0;Write pointer for in-place overwrite

if (arr[read] != '#')Copy character if not backspace

else if (write > 0)Move write pointer back to simulate backspace

return new String(arr, 0, write);Return rebuilt string from char array

#include <iostream>
#include <string>

using namespace std;

string build(string arr) {
    int write = 0;
    for (int read = 0; read < (int)arr.size(); read++) {
        if (arr[read] != '#') {
            arr[write++] = arr[read];
        } else if (write > 0) {
            write--;
        }
    }
    return arr.substr(0, write);
}

bool backspaceCompare(string S, string T) {
    return build(S) == build(T);
}

int main() {
    cout << boolalpha;
    cout << backspaceCompare("ab#c", "ad#c") << '\n'; // true
    cout << backspaceCompare("ab##", "c#d#") << '\n'; // true
    cout << backspaceCompare("a#c", "b") << '\n';     // false
    return 0;
}

Line Notes

int write = 0;Write pointer for in-place overwrite

if (arr[read] != '#')Copy character if not backspace

else if (write > 0)Move write pointer back to simulate backspace

return arr.substr(0, write);Return rebuilt string from substring

return build(S) == build(T);Compare rebuilt strings

function backspaceCompare(S, T) {
    function build(arr) {
        let write = 0;
        for (let read = 0; read < arr.length; read++) {
            if (arr[read] !== '#') {
                arr[write++] = arr[read];
            } else if (write > 0) {
                write--;
            }
        }
        return arr.slice(0, write).join('');
    }
    return build(S.split('')) === build(T.split(''));
}

// Test cases
console.log(backspaceCompare("ab#c", "ad#c")); // true
console.log(backspaceCompare("ab##", "c#d#")); // true
console.log(backspaceCompare("a#c", "b"));     // false

Line Notes

function build(arr)Helper to rebuild string simulating backspaces in-place

let write = 0;Write pointer for overwrite

if (arr[read] !== '#')Copy character if not backspace

else if (write > 0)Move write pointer back to simulate backspace

return arr.slice(0, write).join('')Return rebuilt string

return build(S.split('')) === build(T.split(''))Compare rebuilt strings

⏱

Complexity

TimeO(n + m)

SpaceO(n + m) due to char array conversion

We iterate once over each string and overwrite characters in-place, but converting strings to arrays requires extra space.

💡 For input length 100,000, this means 200,000 operations and memory proportional to input size for arrays.

Interview Verdict: Accepted

This approach is a good compromise between clarity and space optimization, but requires mutable strings.

📊

All Approaches - One-Glance Tradeoffs

💡 The two-pointer from end approach is optimal and recommended for interviews due to its O(1) space and clear logic.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Stack Simulation)	O(n + m)	O(n + m)	No	Yes	Good to mention for clarity, but not optimal to code
2. Two Pointers from End	O(n + m)	O(1)	No	No	Best approach to code in interviews
3. In-Place Rebuild Using Two Pointers Forward	O(n + m)	O(n + m) due to string to array conversion	No	Yes	Good to discuss if mutable strings allowed

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice multiple approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and confirm how backspaces behave.Step 2: Present the brute force stack-based approach to simulate typing.Step 3: Optimize to two pointers from the end to reduce space.Step 4: Optionally discuss in-place rebuilding for further optimization.Step 5: Test with edge cases and explain complexity.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

Interviewer tests your ability to simulate string transformations, optimize space/time, and handle edge cases correctly.

Common Follow-ups

• What if backspace character is different? → Adjust code accordingly.
• How to handle Unicode or multibyte characters? → Use appropriate string handling.

💡 These follow-ups test your adaptability and understanding of string processing nuances.

🔍

Pattern Recognition

When to Use

1) Problem involves strings with backspace or delete operations; 2) Need to compare final processed strings; 3) Backspace affects previous characters; 4) Efficient simulation or two-pointer approach possible.

Signature Phrases

"# means a backspace character""return true if final strings are equal"

NOT This Pattern When

Problems that require substring search or pattern matching without backspace simulation

Similar Problems

Remove All Adjacent Duplicates In String - similar string manipulationValid Parentheses - stack-based character matchingSimplify Path - simulating path navigation with backspaces

Practice

1. Consider the following code snippet implementing the 3Sum Closest algorithm. What is the returned value when the input is nums = [-1, 2, 1, -4] and target = 1?

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]
    for i in range(n - 2):
        left, right = i + 1, n - 1
        while left < right:
            current_sum = nums[i] + nums[left] + nums[right]
            if current_sum == target:
                return current_sum
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            if current_sum < target:
                left += 1
            else:
                right -= 1
    return closest_sum

print(threeSumClosest([-1, 2, 1, -4], 1))

easy

A. 1

B. 4

C. -1

D. 2

Solution

1. Step 1: Sort the array

   Sorted nums = [-4, -1, 1, 2]

2. Step 2: Trace iterations

   i=0: left=1, right=3 current_sum = -4 + (-1) + 2 = -3 (closest_sum init = -4+-1+1 = -4) Update closest_sum to -3 current_sum < target(1), left++ -> left=2 current_sum = -4 + 1 + 2 = -1 Update closest_sum to -1 current_sum < target, left++ -> left=3 (loop ends) i=1: left=2, right=3 current_sum = -1 + 1 + 2 = 2 abs(2-1)=1 < abs(-1-1)=2, update closest_sum=2 current_sum > target, right-- -> right=2 (loop ends) Return closest_sum = 2

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Output matches expected closest sum 2 [OK]

Hint: Sorting and pointer moves yield closest sum 2 [OK]

Common Mistakes:

• Returning initial sum without updates
• Off-by-one pointer increments
• Confusing current_sum with closest_sum

2. You are given an integer array and asked to find all unique triplets that sum to zero. Which approach guarantees an optimal solution in terms of time complexity and handles duplicates efficiently?

easy

A. Sort the array, fix one element, and use a two-pointer approach to find pairs that sum to the negative of the fixed element, skipping duplicates.

B. Use a greedy approach by sorting and picking the smallest and largest elements to form triplets.

C. Use dynamic programming to build up solutions for smaller subsets and combine them to find triplets.

D. Use three nested loops to check all triplets and store unique sorted triplets in a set.

Solution

1. Step 1: Understand problem constraints

   We need all unique triplets summing to zero, efficiently handling duplicates.

2. Step 2: Identify approach that handles duplicates and optimizes search

   Sorting and fixing one element allows using a two-pointer approach to find pairs summing to the complement, skipping duplicates efficiently.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two-pointer approach is O(n^2) and handles duplicates [OK]

Hint: Sorting + two-pointer handles duplicates and runs in O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Using DP which doesn't fit this problem
• Greedy approach misses some triplets

3. You are given an array and a value. You need to remove all occurrences of this value in-place and return the new length of the array after removals. Which approach guarantees an optimal O(n) time and O(1) space solution?

easy

A. Brute force shifting elements left whenever the value is found, resulting in nested loops

B. Two pointers with one scanning from start and the other from end, swapping unwanted elements to the end

C. Sorting the array first, then using binary search to find and remove the value

D. Using a hash set to track elements to keep and reconstruct the array

Solution

1. Step 1: Understand problem constraints

   The problem requires in-place removal with minimal time and space complexity.

2. Step 2: Evaluate approaches

   Brute force shifting is O(n^2), sorting changes order and is O(n log n), hash set uses extra space. Two pointers swapping from start and end achieves O(n) time and O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers swapping approach is optimal and in-place [OK]

Hint: Two pointers swapping from ends -> O(n) in-place removal [OK]

Common Mistakes:

• Confusing sorting or hash sets as optimal in-place solutions

4. What is the time complexity of the optimal two-pointer approach for the 3Sum Smaller problem when the input array has length n?

medium

A. O(n^2) because the outer loop runs n times and the inner two-pointer scan runs in O(n)

B. O(n^3) because of the nested loops

C. O(n log n) due to sorting dominating the complexity

D. O(n^2 log n) because each two-pointer step involves a binary search

Solution

1. Step 1: Identify loops and sorting cost

   Sorting takes O(n log n). The main loop runs O(n) times.

2. Step 2: Analyze inner two-pointer loop

   For each i, two pointers scan the remaining array once, total O(n) per i.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overall time is O(n log n + n^2) -> O(n^2) dominates [OK]

Hint: Two pointers scan each element once per outer iteration [OK]

Common Mistakes:

• Confusing two-pointer scan as O(n^2) per iteration
• Ignoring sorting cost or assuming it dominates
• Assuming binary search is used inside two-pointer

5. If the problem changes so that elements equal to val can appear multiple times and must be removed, but the array is read-only and cannot be modified in-place, which approach is correct?

hard

A. Use the two pointers swap approach to modify the array in-place

B. Use the brute force nested loop shifting approach

C. Create a new array and copy only elements not equal to val, returning its length

D. Sort the array and then remove val elements by slicing

Solution

1. Step 1: Understand read-only constraint

   Cannot modify input array in-place, so approaches that swap or shift in-place are invalid.

2. Step 2: Choose correct approach

   Creating a new array copying only allowed elements respects read-only constraint and removes val elements.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   New array creation is necessary when input is immutable [OK]

Hint: Read-only input -> must copy to new array [OK]

Common Mistakes:

• Trying to modify read-only array in-place
• Using inefficient nested loops unnecessarily