Two Sum II - Input Array Is Sorted

📋

Two Sum II - Input Array Is Sorted

Edge cases:

</>

IDE

def two_sum_brute(numbers: list[int], target: int) -> list[int]:public int[] twoSum(int[] numbers, int target)vector<int> twoSum(vector<int>& numbers, int target)function twoSum(numbers, target)

def two_sum_brute(numbers, target):
    # Write your solution here
    pass

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // Write your solution here
        return new int[2];
    }
}

#include <vector>
using namespace std;

vector<int> twoSum(vector<int>& numbers, int target) {
    // Write your solution here
    return {};
}

function twoSum(numbers, target) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [0, 1]Using zero-based indices instead of 1-based indices.✅ Return indices as i+1 and j+1 instead of i and j.

Wrong: [1, 3]Incorrect pointer movement causing skipping the correct pair.✅ Move left pointer right if sum < target; move right pointer left if sum > target.

Wrong: []Returning empty list even when solution exists due to incorrect loop conditions.✅ Ensure loop continues while left < right and checks all pairs.

Wrong: [1, 2]Fails on duplicates by always returning first two elements regardless of sum.✅ Check sum of elements at pointers before returning indices.

Wrong: TLEUsing brute force O(n^2) approach on large input.✅ Implement two-pointer O(n) approach to pass performance test.

✓

Test Cases

Focus on handling smallest and boundary inputs correctly.

Consider tricky cases like duplicates, negatives, and no solution scenarios.

Optimize your solution to linear time to handle large inputs efficiently.

t1_01basic

Input{"numbers":[2,7,11,15],"target":9}

Expected[1,2]

⏱ Performance - must finish in 2000ms

2 + 7 = 9, so return indices 1 and 2.

💡 Try using two pointers starting at opposite ends of the array.

💡 Move pointers inward depending on whether the sum is less or greater than the target.

💡 Return the 1-based indices of the two numbers when their sum equals the target.

Why it failed: Returned wrong indices or sum incorrect; likely pointer movement logic is flawed. Fix by correctly moving left pointer right if sum < target, else move right pointer left.

✓ Correctly identified the two indices summing to target using two pointers.

t1_02basic

Input{"numbers":[1,2,3,4,4,9,56,90],"target":8}

Expected[4,5]

⏱ Performance - must finish in 2000ms

4 + 4 = 8, indices 4 and 5.

💡 Remember the array is sorted; duplicates may exist.

💡 Check pairs by moving pointers inward until sum matches target.

💡 Return the first pair found that sums to target with 1-based indices.

Why it failed: Incorrect output due to not handling duplicates or pointer updates properly. Fix by ensuring pointers move correctly and duplicates are allowed as separate elements.

✓ Correctly found the pair of indices summing to target including duplicates.

t2_01edge

Input{"numbers":[1,2],"target":3}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Array with only two elements; sum is target.

💡 Test the smallest valid input size.

💡 Check if your code handles arrays of length 2 correctly.

💡 Return indices [1, 2] when the two elements sum to target.

Why it failed: Fails on smallest input size; likely indexing or loop boundary error. Fix by ensuring code handles arrays of length exactly 2.

✓ Correctly handles minimal input size with two elements.

t2_02edge

Input{"numbers":[1,2,3,4,5],"target":6}

Expected[1,5]

⏱ Performance - must finish in 2000ms

Sum of first and last elements equals target.

💡 Test the two-pointer extremes: first and last elements.

💡 Ensure pointers start at opposite ends and check sums correctly.

💡 Return indices [1, 5] when sum of first and last elements equals target.

Why it failed: Fails to find pair at array ends; likely pointer initialization or update bug. Fix by initializing left=0 and right=n-1 and moving pointers correctly.

✓ Correctly finds pair at opposite ends of the array.

t2_03edge

Input{"numbers":[2,2,2,2],"target":4}

Expected[1,2]

⏱ Performance - must finish in 2000ms

All elements identical; target is twice that element.

💡 Test handling of duplicates where multiple pairs possible.

💡 Ensure the solution returns the first valid pair.

💡 Return indices [1, 2] for the first two elements summing to target.

Why it failed: Fails on duplicates; likely skipping or mishandling equal elements. Fix by allowing pointers to move even if elements are equal and returning first valid pair.

✓ Correctly handles duplicates and returns first valid pair.

t2_04edge

Input{"numbers":[1],"target":2}

Expected[]

⏱ Performance - must finish in 2000ms

Single element array; no pair possible.

💡 Test input with only one element.

💡 Your code should handle cases where no pair exists.

💡 Return empty list if no valid pair found.

Why it failed: Fails by returning invalid indices or crashing on single element input. Fix by checking array length before processing pairs.

✓ Correctly returns empty list for single element input.

t3_01corner

Input{"numbers":[1,2,3,4,5],"target":10}

Expected[]

⏱ Performance - must finish in 2000ms

No two numbers sum to target; problem states one solution but test robustness.

💡 Consider what your code returns if no pair sums to target.

💡 Check if your code handles no solution gracefully.

💡 Return empty list if no valid pair found, even if problem states one solution.

Why it failed: Fails by returning invalid indices or crashing when no pair sums to target. Fix by returning empty list if no pair found.

✓ Gracefully handles no solution case by returning empty list.

t3_02corner

Input{"numbers":[-3,3,4,90],"target":0}

Expected[1,2]

⏱ Performance - must finish in 2000ms

Test negative and positive numbers summing to zero.

💡 Check if your code handles negative numbers correctly.

💡 Two pointers should move inward based on sum compared to target.

💡 Return indices of pair summing to zero, e.g. [-3, 3].

Why it failed: Fails on negative numbers; likely pointer movement or sum comparison bug. Fix by correctly comparing sum to target including negatives.

✓ Correctly handles negative and positive numbers summing to target.

t3_03corner

Input{"numbers":[1,2,3,4,4,9,56,90],"target":8}

Expected[4,5]

⏱ Performance - must finish in 2000ms

Greedy trap: picking first pair that sums over target instead of moving pointers correctly.

💡 Beware of greedy approach that picks first pair over target.

💡 Two pointers must move inward properly to find exact sum.

💡 If sum > target, move right pointer left; if sum < target, move left pointer right.

Why it failed: Fails due to greedy pointer movement; fix by adjusting pointers based on sum comparison rather than first match.

✓ Correctly avoids greedy trap and finds correct pair.

t4_01performance

Input{"numbers":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100000],"target":100099}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000, O(n) two-pointer approach must complete within 2 seconds.

💡 Use two pointers starting at opposite ends for O(n) time.

💡 Avoid nested loops which cause O(n^2) time and TLE.

💡 Increment or decrement pointers based on sum compared to target.

Why it failed: TLE due to O(n^2) brute force approach; fix by implementing two-pointer O(n) solution.

✓ Efficient O(n) two-pointer solution passes performance test.

Practice

1. You are given an integer array and a target integer. The task is to find three integers in the array whose sum is closest to the target. Which approach guarantees an optimal solution with O(n²) time complexity?

easy

A. Sort the array and use a fixed pointer with two pointers scanning from both ends.

B. Use a brute force triple nested loop to check all triplets.

C. Apply dynamic programming to store sums of pairs and find closest triplet sum.

D. Use a greedy approach by picking the closest element to target and then two others.

Solution

1. Step 1: Understand problem constraints

   The problem requires finding three numbers whose sum is closest to a target, which suggests checking combinations efficiently.

2. Step 2: Identify approach with O(n²) complexity

   Sorting the array allows fixing one element and using two pointers to find pairs that sum closest to the remaining target, achieving O(n²) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting + two pointers is classic for 3Sum Closest [OK]

Hint: Sorting + two pointers reduces complexity to O(n²) [OK]

Common Mistakes:

• Thinking brute force is optimal
• Confusing DP with this problem
• Assuming greedy works for closest sum

2. Consider the following Python code implementing the optimal two-pointer forward approach for backspace string compare. What is the value of the variable write after processing the input string S = "ab#c" inside the build function?

easy

A. 2

B. 3

C. 4

D. 1

Solution

1. Step 1: Trace the build function with input "ab#c"

   Start with write=0. Read 'a' -> arr[0]='a', write=1. Read 'b' -> arr[1]='b', write=2. Read '#' -> write=1 (backspace removes 'b'). Read 'c' -> arr[1]='c', write=2.

2. Step 2: Final value of write

   After processing, write=2, indicating the final string length is 2 ("ac").

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   write increments and decrements correctly for backspace [OK]

Hint: write increments on char, decrements on backspace if possible [OK]

Common Mistakes:

• Counting '#' as a character and incrementing write
• Not decrementing write on backspace
• Off-by-one errors in write pointer

3. Consider the following code snippet for removing duplicates from a sorted array allowing at most two duplicates. What is the value of write_index after processing the input [1,1,2]?

easy

A. 2

B. 1

C. 3

D. 0

Solution

1. Step 1: Trace write_index and read_index for input [1,1,2]

   Initially, write_index=0. Iteration 0: write_index<2, write 1, write_index=1. Iteration 1: write_index=1<2, write 1, write_index=2. Iteration 2: nums[2]=2 != nums[0]=1, write 2, write_index=3.

2. Step 2: Final write_index value

   After processing all elements, write_index=3, indicating the length of the modified array.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   All elements allowed, write_index matches array length [OK]

Hint: write_index increments for allowed duplicates [OK]

Common Mistakes:

• Off-by-one errors in write_index
• Confusing read_index with write_index
• Not handling first two elements separately

4. You are given a problem where you must reverse the order of characters in an array in-place, without using extra space. Which algorithmic approach best guarantees an optimal solution in terms of time and space complexity?

easy

A. Using two pointers starting at opposite ends of the array and swapping elements until they meet.

B. Using a brute force approach that creates a new array and copies elements in reverse order.

C. Using a dynamic programming approach to store intermediate reversed substrings.

D. Using a greedy approach that swaps characters only when they are vowels.

Solution

1. Step 1: Understand the problem constraints

   The problem requires reversing characters in-place without extra space, so approaches that use additional arrays are suboptimal.

2. Step 2: Identify the optimal approach

   Two pointers starting at opposite ends allow swapping characters in O(n) time and O(1) extra space, fulfilling the problem requirements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Two-pointer in-place reversal is standard for optimal string reversal [OK]

Hint: Two pointers from ends swap in-place efficiently [OK]

Common Mistakes:

• Thinking DP or greedy applies to reversing strings
• Assuming extra space is allowed
• Confusing brute force with optimal in-place

5. Suppose the 3Sum problem is modified so that elements can be reused multiple times in a triplet (e.g., triplet [0,0,0] is valid if zeros exist). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Remove the duplicate skipping for fixed element i and inner pointer j, allowing repeated elements.

B. Use three nested loops to allow repeated indices and check sums directly.

C. Keep the same code but remove the sorting step to allow duplicates naturally.

D. Modify the hash set approach to not skip duplicates and allow complement to be equal to nums[j].

Solution

1. Step 1: Understand reuse means duplicates allowed in triplets

   Allowing reuse means complement can be equal to nums[j], so skipping duplicates must be adjusted.

2. Step 2: Modify hash set approach accordingly

   Do not skip duplicates; allow complement == nums[j]; sorting still needed to avoid unordered duplicates.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Allowing complement == nums[j] and no skipping duplicates handles reuse correctly [OK]

Hint: Allow complement == nums[j] and no skipping duplicates for reuse [OK]

Common Mistakes:

• Removing sorting breaks uniqueness
• Using triple loops is inefficient
• Removing duplicate skipping blindly causes duplicates