Two Sum

📋

Two Sum

Edge cases:

</>

IDE

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

def two_sum(nums, target):
    # Write your solution here
    pass

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

#include <vector>
using namespace std;

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

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

Common Bugs to Avoid

Wrong: [-1, -1]Returning default or error indices instead of valid pair.✅ Ensure to return indices immediately when complement found; do not return default values.

Wrong: [0,0]Using same element twice instead of two distinct indices.✅ Check complement in map before inserting current index to avoid using same element twice.

Wrong: [0,2]Greedy approach picking wrong pair or incorrect order.✅ Use hash map complement lookup and return first valid pair found during iteration.

Wrong: No output or timeoutUsing nested loops causing O(n^2) time complexity.✅ Implement hash map complement lookup for O(n) time complexity.

Wrong: [1,3]Returning wrong pair when multiple pairs possible.✅ Return the first valid pair found during iteration as guaranteed unique answer.

✓

Test Cases

Try testing your solution on minimal and negative number inputs.

Consider tricky cases with duplicates and multiple valid pairs.

Optimize your solution to run in linear time using a hash map.

t1_01basic

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

Expected[0,1]

⏱ Performance - must finish in 2000ms

nums[0] + nums[1] = 2 + 7 = 9

💡 Think about using a hash map to find complements efficiently.

💡 Check if the complement (target - current number) exists in the map.

💡 Return indices as soon as you find a complement to avoid extra loops.

Why it failed: Returned wrong indices or no pair found. Possibly forgot to check complement existence before inserting current number. Fix by checking complement first, then inserting current index.

✓ Correct pair indices found using complement lookup.

t1_02basic

Input{"nums":[3,2,4],"target":6}

Expected[1,2]

⏱ Performance - must finish in 2000ms

nums[1] + nums[2] = 2 + 4 = 6

💡 Try iterating once and storing indices in a map.

💡 For each number, check if target - number is already in the map.

💡 Return the stored index and current index when complement found.

Why it failed: Incorrect output due to not handling complement lookup properly. Fix by checking complement in map before inserting current number.

✓ Correct indices returned for second basic test.

t2_01edge

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

Expected[0,1]

⏱ Performance - must finish in 2000ms

Only two elements, sum to target exactly.

💡 Check behavior with smallest input size.

💡 Ensure your code handles arrays of length 2 correctly.

💡 Return indices [0,1] when sum matches target.

Why it failed: Fails on minimal input size. Possibly loops or map usage assumes more elements. Fix by handling arrays of length 2 properly.

✓ Handles minimal input size correctly.

t2_02edge

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

Expected[0,2]

⏱ Performance - must finish in 2000ms

nums[0] + nums[2] = -3 + 3 = 0, includes negative numbers.

💡 Test with negative numbers included.

💡 Ensure complement lookup works with negative values.

💡 Check that map keys handle negative integers correctly.

Why it failed: Fails with negative numbers. Possibly map keys or complement calculation incorrect. Fix by correctly computing complement and using map for negative keys.

✓ Correctly handles negative numbers.

t2_03edge

Input{"nums":[0,4,3,0],"target":0}

Expected[0,3]

⏱ Performance - must finish in 2000ms

Target zero with zeros in array; nums[0] + nums[3] = 0 + 0 = 0.

💡 Test with zeros and target zero.

💡 Ensure duplicates and zero values are handled correctly.

💡 Check that complement lookup finds the correct zero pair.

Why it failed: Fails to find zero pair. Possibly map overwrites indices or misses duplicates. Fix by storing first occurrence and checking complement before insertion.

✓ Correctly finds zero pair for target zero.

t2_04edge

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

Expected[0,1]

⏱ Performance - must finish in 2000ms

Exact boundary case with two identical elements summing to target.

💡 Test exact boundary with duplicates.

💡 Ensure complement lookup handles duplicates correctly.

💡 Return indices of two distinct elements even if values are same.

Why it failed: Fails to handle duplicates properly. Fix by checking complement before inserting current index to avoid using same element twice.

✓ Correctly handles exact boundary with duplicates.

t3_01corner

Input{"nums":[1,2,3,4,5],"target":7}

Expected[1,4]

⏱ Performance - must finish in 2000ms

nums[1] + nums[4] = 2 + 5 = 7; tests greedy trap of picking first complement found.

💡 Beware of greedy approaches that pick first complement without checking all.

💡 Use a hash map to store indices and check complements properly.

💡 Return the first valid pair found by complement lookup, not just any pair.

Why it failed: Fails due to greedy approach picking wrong pair or order. Fix by using hash map complement lookup and returning first valid pair indices.

✓ Correctly avoids greedy trap and returns valid pair.

t3_02corner

Input{"nums":[3,3],"target":6}

Expected[0,1]

⏱ Performance - must finish in 2000ms

Tests handling of duplicates and 0/1 usage constraint; must not reuse same element twice.

💡 Check that you do not use the same element twice.

💡 Store indices and check complement before inserting current index.

💡 Return indices of two distinct elements that sum to target.

Why it failed: Fails by reusing same element index twice or returning invalid pair. Fix by checking complement in map before inserting current index.

✓ Correctly handles duplicates and 0/1 usage constraint.

t3_03corner

Input{"nums":[1,5,1,5],"target":10}

Expected[1,3]

⏱ Performance - must finish in 2000ms

Tests multiple pairs possible but only one valid answer guaranteed; must return correct pair.

💡 Multiple pairs may sum to target; only one valid answer exists.

💡 Use complement lookup to find first valid pair.

💡 Return indices of the pair that appears first in iteration.

Why it failed: Fails by returning wrong pair or multiple pairs. Fix by returning first valid pair found during iteration.

✓ Correctly returns the guaranteed unique valid pair.

t4_01performance

Input{"nums":[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,100],"target":199}

Expectednull

⏱ Performance - must finish in 2000ms

Large input n=100, testing O(n) hash map approach completes within time limit.

💡 Use a hash map for O(n) complement lookup.

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

💡 Check complement existence before inserting current index.

Why it failed: TLE due to nested loops or inefficient approach. Fix by implementing O(n) hash map complement lookup.

✓ Efficient O(n) solution passes within time limit.

Practice

1. Consider the following Python function to find the longest contiguous subarray with equal number of 0s and 1s. What is the returned value when the input is [0, 1, 0, 1]?

def findMaxLength(nums):
    prefix_sum = 0
    seen = {0: -1}
    max_length = 0
    for i, num in enumerate(nums):
        prefix_sum += 1 if num == 1 else -1
        if prefix_sum in seen:
            max_length = max(max_length, i - seen[prefix_sum])
        else:
            seen[prefix_sum] = i
    return max_length

easy

A. 4

B. 2

C. 3

D. 0

Solution

1. Step 1: Trace prefix sums and seen map

   Index 0: num=0 -> prefix_sum=-1, seen={0:-1, -1:0}, max_length=0 Index 1: num=1 -> prefix_sum=0, seen has 0 at -1, max_length=max(0,1-(-1))=2 Index 2: num=0 -> prefix_sum=-1, seen has -1 at 0, max_length=max(2,2-0)=2 Index 3: num=1 -> prefix_sum=0, seen has 0 at -1, max_length=max(2,3-(-1))=4

2. Step 2: Return max_length

   max_length is 4, the length of the entire array.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Full array balanced, max_length=4 [OK]

Hint: Prefix sums track balance; max length updates on repeated sums [OK]

Common Mistakes:

• Off-by-one errors in length calculation
• Ignoring initial seen entry for sum 0
• Confusing prefix sum updates

2. Consider the following buggy code for detecting if a number is happy. Which line contains the subtle bug that can cause incorrect results or infinite loops?

def sum_of_squares(num):
    return sum(int(d) ** 2 for d in str(num))

UNHAPPY_CYCLE = {4, 16, 37, 58, 89, 145, 42, 20}

def isHappy(n: int) -> bool:
    while n != 1 and n not in UNHAPPY_CYCLE:
        n = sum_of_squares(n)
    return true

medium

A. Line 8: return true statement

B. Line 6: while loop condition

C. Line 2: sum_of_squares function implementation

D. Line 7: updating n with sum_of_squares(n)

Solution

1. Step 1: Analyze return statement

   The function returns true unconditionally after loop ends, ignoring if n is in unhappy cycle.

2. Step 2: Identify correct return logic

   Should return n == 1 to distinguish happy from unhappy numbers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect return causes false positives [OK]

Hint: Return must check if n == 1 after loop [OK]

Common Mistakes:

• Returning true always after loop
• Ignoring unhappy cycle detection

3. The following code attempts to find the longest subarray with sum divisible by k. Identify the line containing the subtle bug that causes incorrect results for arrays containing negative numbers.

def longest_subarray_div_by_k(nums, k):
    earliest = [-2] * k
    earliest[0] = -1
    max_length = 0
    prefix_sum = 0
    for i, num in enumerate(nums):
        prefix_sum += num
        remainder = prefix_sum % k
        # Bug: missing adjustment for negative remainder
        if earliest[remainder] != -2:
            max_length = max(max_length, i - earliest[remainder])
        else:
            earliest[remainder] = i
    return max_length

medium

A. Line computing remainder = prefix_sum % k

B. Line initializing earliest[0] = -1

C. Line updating max_length = max(max_length, i - earliest[remainder])

D. Line setting earliest[remainder] = i

Solution

1. Step 1: Identify remainder calculation

   When prefix_sum is negative, prefix_sum % k in Python returns a non-negative remainder, but in some languages or implementations it can be negative. The code lacks adjustment for negative remainder.

2. Step 2: Why this causes bugs

   If remainder is negative, indexing earliest array causes errors or misses correct subarrays. The fix is to add if remainder < 0: remainder += k.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Negative prefix sums require remainder adjustment [OK]

Hint: Check remainder calculation for negative sums [OK]

Common Mistakes:

• Forgetting to adjust negative remainders
• Misinitializing earliest array
• Updating max_length incorrectly

4. What is the time complexity of the get operation in the optimal time-based key-value store implementation that uses a hash map with sorted timestamp lists and binary search?

medium

A. O(log n), where n is the number of timestamps stored for the key

B. O(n), where n is the number of timestamps stored for the key

C. O(log m), where m is the total number of keys stored

D. O(1), constant time due to hash map usage

Solution

1. Step 1: Identify the data structure used for retrieval

   Retrieval uses binary search on a sorted list of timestamps for the given key.

2. Step 2: Analyze binary search complexity

   Binary search on n timestamps takes O(log n) time. Hash map lookup is O(1) average but the dominant cost is binary search.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Binary search on timestamps list dominates get operation time [OK]

Hint: Binary search on timestamps list is O(log n) [OK]

Common Mistakes:

• Confusing total keys with timestamps count
• Assuming hash map makes get O(1) ignoring binary search
• Mistaking linear search complexity for get

5. What is the time complexity of the optimal frequency counting approach for checking if two strings of length n are anagrams, assuming the strings contain only lowercase English letters?

medium

A. O(n log n) due to sorting the strings

B. O(n) because each string is traversed once and frequency updates are O(1)

C. O(n * 26) because for each character you update a frequency array of size 26

D. O(1) since the frequency array size is fixed and independent of input length

Solution

1. Step 1: Identify loops over input strings

   Both strings are traversed once, each iteration doing O(1) work updating counts.

2. Step 2: Analyze frequency array operations

   Frequency array is fixed size 26, so updates are constant time, not multiplied by n.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Overall time is linear in string length n [OK]

Hint: Frequency updates are O(1), total O(n) time [OK]

Common Mistakes:

• Confusing sorting complexity with counting
• Multiplying by 26 unnecessarily
• Assuming constant time overall