Two Sum Problem Classic Hash Solution in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the hash map for storing numbers and their indices.

DSA C

int hashMap[[1]];

Drag options to blanks, or click blank then click option'

A100

B1000

C10

D100000

Attempts:

3 left

💡 Hint

Common Mistakes

Using too small a size causing collisions or out-of-bound errors.

Using an uninitialized or zero-sized array.

The hash map size is set to 100000 to cover the range of possible input values efficiently.

2fill in blank

medium

Complete the code to initialize the hash map values to -1 indicating empty slots.

DSA C

for (int i = 0; i < [1]; i++) {
    hashMap[i] = -1;
}

Drag options to blanks, or click blank then click option'

A100000

B1000

C100

D10

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing fewer elements than the hash map size.

Not initializing the hash map at all.

The loop runs up to 100000 to initialize all hash map entries to -1.

3fill in blank

hard

Fix the error in the condition to check if the complement exists in the hash map.

DSA C

if (hashMap[[1]] != -1) {
    return (int[]){hashMap[complement], i};
}

Drag options to blanks, or click blank then click option'

Acomplement

Bnums[i]

Ci

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Checking hashMap[nums[i]] instead of hashMap[complement].

Using the wrong variable in the condition.

The complement is the key to check in the hash map to find if the pair exists.

4fill in blank

hard

Fill both blanks to store the current index in the hash map and calculate the complement.

DSA C

int complement = [1] - nums[i];
hashMap[[2]] = i;

Drag options to blanks, or click blank then click option'

Atarget

Bnums[i]

Ci

Dcomplement

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping complement and nums[i] in assignments.

Storing complement instead of nums[i] in hash map.

The complement is target minus current number, and we store the current index at nums[i] in the hash map.

5fill in blank

hard

Fill all three blanks to complete the Two Sum function returning indices of the two numbers.

DSA C

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    static int hashMap[100000];
    for (int i = 0; i < [1]; i++) {
        hashMap[i] = -1;
    }
    for (int i = 0; i < numsSize; i++) {
        int complement = [2] - nums[i];
        if (hashMap[complement] != -1) {
            int* result = malloc(2 * sizeof(int));
            result[0] = hashMap[complement];
            result[1] = i;
            *returnSize = 2;
            return result;
        }
        hashMap[[3]] = i;
    }
    *returnSize = 0;
    return NULL;
}

Drag options to blanks, or click blank then click option'

A100000

Btarget

Cnums[i]

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong loop size for initialization.

Mixing up complement and nums[i] in hash map access.

Not allocating memory for the result array.

The hash map is initialized with size 100000. The complement is target - nums[i]. We store the index i at hashMap[nums[i]].

Practice

1. What is the main purpose of using a hash map in the classic Two Sum problem solution?

easy

A. To store all pairs of numbers

B. To sort the array before searching

C. To store numbers and their indices for quick lookup

D. To reverse the array elements

Solution

1. Step 1: Understand the role of hash map in Two Sum

   The hash map stores each number as a key and its index as the value for quick lookup.

2. Step 2: Explain why quick lookup is needed

   Quick lookup helps find if the complement (target - current number) exists without scanning the entire array again.

3. Final Answer:

   To store numbers and their indices for quick lookup -> Option C

4. Quick Check:

   Hash map = quick lookup [OK]

Hint: Hash map stores values for instant complement search [OK]

Common Mistakes:

• Thinking hash map sorts the array
• Assuming hash map stores all pairs
• Confusing hash map with array reversal

2. Which of the following is the correct syntax to declare a hash map (dictionary) in C for the Two Sum problem?

easy

A. unordered_map hashmap;

B. int hashmap[1000];

C. map hashmap = new map();

D. dict hashmap = {};

Solution

1. Step 1: Identify C++ STL syntax for hash map

   In C++, unordered_map is used for hash maps with integer keys and values.

2. Step 2: Check other options for correctness

   int hashmap[1000]; is a fixed-size array, not a hash map. map hashmap = new map(); is invalid syntax. dict hashmap = {}; is Python syntax.

3. Final Answer:

   unordered_map hashmap; -> Option A

4. Quick Check:

   unordered_map = hash map in C++ [OK]

Hint: Use unordered_map for hash map in C++ [OK]

Common Mistakes:

• Using array instead of hash map
• Confusing Python or Java syntax with C++
• Incorrect map declaration syntax

3. What will be the output of the following code snippet for input nums = [2, 7, 11, 15], target = 9?

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    unordered_map map;
    for (int i = 0; i < numsSize; i++) {
        int complement = target - nums[i];
        if (map.find(complement) != map.end()) {
            int* result = (int*)malloc(2 * sizeof(int));
            result[0] = map[complement];
            result[1] = i;
            *returnSize = 2;
            return result;
        }
        map[nums[i]] = i;
    }
    *returnSize = 0;
    return NULL;
}

medium

A. [1, 0]

B. [0, 1]

C. [2, 3]

D. NULL

Solution

1. Step 1: Trace the loop and hash map insertions

   At i=0, map = {2:0}. At i=1, complement = 9-7=2 found in map at index 0.

2. Step 2: Return indices of complement and current number

   Return [0,1] as the pair that sums to 9.

3. Final Answer:

   [0, 1] -> Option B

4. Quick Check:

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

Hint: Check complement in map before inserting current number [OK]

Common Mistakes:

• Returning indices in wrong order
• Not checking complement before insertion
• Returning NULL when pair exists

4. Identify the bug in this Two Sum hash map solution snippet:

for (int i = 0; i < numsSize; i++) {
    map[nums[i]] = i;
    int complement = target - nums[i];
    if (map.find(complement) != map.end()) {
        return {map[complement], i};
    }
}

medium

A. Loop should start from i = 1

B. map should store complement instead of current number

C. Return statement syntax is invalid in C

D. Complement check should happen before inserting current number

Solution

1. Step 1: Analyze order of operations in loop

   Current number is inserted before checking complement, causing false positive when complement equals current number.

2. Step 2: Correct order to check complement before insertion

   Check if complement exists in map first, then insert current number to avoid matching with itself.

3. Final Answer:

   Complement check should happen before inserting current number -> Option D

4. Quick Check:

   Check complement before insert [OK]

Hint: Check complement before adding current number to map [OK]

Common Mistakes:

• Inserting before checking complement
• Wrong return syntax in C
• Starting loop from wrong index

5. Given an array nums = [3, 3, 4, 5] and target = 6, what will the Two Sum hash map solution return and why?

hard

A. [0, 1] because nums[0] + nums[1] = 3 + 3 = 6

B. [2, 3] because nums[2] + nums[3] = 4 + 5 = 9

C. NULL because no two numbers sum to 6

D. [1, 0] because indices order is reversed

Solution

1. Step 1: Trace the hash map insertions and complement checks

   At i=0, map = {3:0}. At i=1, complement = 6-3=3 found at index 0.

2. Step 2: Return indices of the first valid pair

   Return [0,1] as the pair that sums to 6.

3. Final Answer:

   [0, 1] because nums[0] + nums[1] = 3 + 3 = 6 -> Option A

4. Quick Check:

   3 + 3 = 6 [OK]

Hint: Duplicates can form valid pairs if sum matches target [OK]

Common Mistakes:

• Ignoring duplicate values
• Returning wrong indices order
• Assuming no pair exists when duplicates present