Intersection of Two Arrays II

▶

Steps

setup

Sort nums1

The algorithm sorts nums1 from [1,2,2,1] to [1,1,2,2] to prepare for efficient comparison.

💡 Sorting ensures elements are in order, making it easier to find intersections by linear traversal.

Line:

nums1.sort()

💡 Sorting is a prerequisite for the two-pointer technique to work correctly.

setup

Sort nums2

The algorithm sorts nums2 from [2,2] to [2,2], which is already sorted but this step confirms order.

💡 Sorting both arrays is necessary for the two-pointer approach to work correctly.

Line:

nums2.sort()

💡 Even if nums2 is already sorted, this step ensures consistency in the algorithm.

compare

Compare nums1[i] and nums2[j]

Compare nums1[0] = 1 and nums2[0] = 2 to decide which pointer to move.

💡 Comparing elements at pointers determines if we found a match or which pointer to advance.

Line:

if nums1[i] == nums2[j]:

💡 Since 1 < 2, nums1's pointer moves forward to find a potential match.

traverse

Increment i pointer

Move pointer i from 0 to 1 to check next element in nums1 against nums2[j].

💡 Advancing pointer i skips the smaller element to try to find a match.

Line:

i += 1

💡 Pointer i moves forward to compare the next element with nums2[j].

compare

Compare nums1[i] and nums2[j]

Compare nums1[1] = 1 and nums2[0] = 2 to decide next pointer movement.

💡 We check if the current elements match or which pointer to move next.

Line:

if nums1[i] == nums2[j]:

💡 Again, nums1[i] is smaller, so we move i forward to find a match.

traverse

Increment i pointer

Move pointer i from 1 to 2 to check next element in nums1 against nums2[j].

💡 Moving pointer i forward to continue searching for a match.

Line:

i += 1

💡 Pointer i advances to the next element for comparison.

compare

Compare nums1[i] and nums2[j]

Compare nums1[2] = 2 and nums2[0] = 2 to check for intersection.

💡 If elements are equal, we add to intersection and move both pointers.

Line:

if nums1[i] == nums2[j]:

💡 Found a common element 2, so add it to the intersection list.

insert

Add element to intersection and increment both pointers

Add 2 to intersection list, increment i from 2 to 3 and j from 0 to 1.

💡 Adding matched element to result and moving both pointers to continue search.

Line:

intersection.append(nums1[i])
i += 1
j += 1

💡 Both pointers move forward after a successful match to avoid duplicate counting.

compare

Compare nums1[i] and nums2[j]

Compare nums1[3] = 2 and nums2[1] = 2 to check for another intersection.

💡 Check if the next elements match to add more to the intersection.

Line:

if nums1[i] == nums2[j]:

💡 Found another common element 2, add it to intersection.

insert

Add element to intersection and increment both pointers

Add 2 to intersection list, increment i from 3 to 4 and j from 1 to 2.

💡 Add the matched element and move pointers beyond array bounds to end loop.

Line:

intersection.append(nums1[i])
i += 1
j += 1

💡 Pointers move beyond array length, ending the while loop.

reconstruct

End loop and return intersection

Both pointers have reached the end of their arrays, so the algorithm returns the intersection list [2, 2].

💡 When either pointer reaches the end, no more comparisons are possible.

Line:

return intersection

💡 The final intersection contains all common elements including duplicates.

def intersect(nums1, nums2):
    nums1.sort()  # STEP 1
    nums2.sort()  # STEP 2
    i, j = 0, 0  # initialize pointers
    intersection = []  # result list
    while i < len(nums1) and j < len(nums2):  # loop condition
        if nums1[i] == nums2[j]:  # STEP 3,7,9 compare elements
            intersection.append(nums1[i])  # STEP 8,10 add to intersection
            i += 1  # STEP 8,10 increment i
            j += 1  # STEP 8,10 increment j
        elif nums1[i] < nums2[j]:  # STEP 3,5 compare elements
            i += 1  # STEP 4,6 increment i
        else:
            j += 1
    return intersection  # STEP 11

if __name__ == '__main__':
    print(intersect([1,2,2,1], [2,2]))  # Output: [2, 2]

📊

Intersection of Two Arrays II - Watch the Algorithm Execute, Step by Step

Watching each pointer move and comparison helps you understand how the algorithm finds common elements efficiently without extra space.

insert

nums1→[1,1,2,2]

nums2→[2,2]

intersection→[]

i→0

j→0

insert

nums1→[1,1,2,2]

nums2→[2,2]

intersection→[]

i→0

j→0

check

nums1[i]→1

nums2[j]→2

intersection→[]

i→0

j→0

increment

nums1[i]→1

nums2[j]→2

intersection→[]

i→1

j→0

check

nums1[i]→1

nums2[j]→2

intersection→[]

i→1

j→0

increment

nums1[i]→2

nums2[j]→2

intersection→[]

i→2

j→0

check

nums1[i]→2

nums2[j]→2

intersection→[]

i→2

j→0

Result: [2]

insert

nums1[i]→2

nums2[j]→2

intersection→[2]

i→3

j→1

Result: [2]

check

nums1[i]→2

nums2[j]→2

intersection→[2]

i→3

j→1

Result: [2,2]

insert

intersection→[2,2]

i→4

j→2

Result: [2,2]

check

intersection→[2,2]

Result: [2,2]

Key Takeaways

✓ Sorting both arrays enables efficient linear traversal to find intersections.

Without sorting, the two-pointer technique wouldn't work; sorting is the foundation.

✓ Pointers move forward only when elements are matched or the smaller element is skipped.

This pointer movement avoids unnecessary comparisons and handles duplicates correctly.

✓ The intersection list grows only when elements at both pointers are equal.

This ensures duplicates are counted correctly and no extra elements are added.

Practice

1. Consider the following code snippet that checks if two strings are anagrams. What is the value of the count array after processing the first string s = "abc" and before processing the second string t = "bca"?

easy

A. [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

B. [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

C. [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

D. [0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Solution

1. Step 1: Increment counts for each character in "abc"

   For 'a', index 0 -> count[0] = 1; for 'b', index 1 -> count[1] = 1; for 'c', index 2 -> count[2] = 1.

2. Step 2: Confirm count array state before processing second string

   All other indices remain 0, so count = [1,1,1,0,...,0].

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Counting characters matches expected frequency array [OK]

Hint: Count increments match characters in s exactly [OK]

Common Mistakes:

• Off-by-one indexing in count array
• Resetting count before second loop
• Confusing increments with decrements

2. The following code attempts to detect a continuous subarray sum divisible by k. Which line contains a subtle bug that can cause incorrect results on some inputs?

medium

A. Line 7: normalizing k if negative

B. Line 9: computing total modulo k without handling negative values

C. Line 3: initializing remainder_map with {0: -1}

D. Line 12: checking if subarray length > 1

Solution

1. Step 1: Identify modulo operation on line 9

   The code uses total = total % k without adjusting for negative totals, which can yield negative remainders.

2. Step 2: Understand impact of negative remainders

   Negative remainders cause incorrect remainder_map keys, missing valid subarrays.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Modulo must be normalized to non-negative remainder [OK]

Hint: Modulo with negatives must be normalized to positive remainder [OK]

Common Mistakes:

• Not normalizing modulo results for negative sums
• Overwriting remainder_map entries instead of preserving earliest index
• Allowing subarrays of length 1 to return True

3. What is the time complexity of the optimal Happy Number detection algorithm that uses a known set of unhappy cycle numbers and repeatedly computes the sum of squares of digits until termination?

medium

A. O(n) where n is the input number

B. O(k * n) where k is iterations and n is the number of digits

C. O(log n) because each iteration reduces the number size drastically

D. O(k * log n) where k is the number of iterations until 1 or cycle

Solution

1. Step 1: Identify cost per iteration

   Each iteration computes sum of squares of digits, which takes O(log n) time since number of digits is proportional to log n.

2. Step 2: Count iterations until termination

   There are k iterations until number reaches 1 or cycle; total time is O(k * log n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Time depends on iterations and digit count, not linear in n [OK]

Hint: Sum of squares per iteration costs O(log n) [OK]

Common Mistakes:

• Confusing input size n with number of digits
• Assuming linear O(n) time

4. The following code attempts to count subarrays summing to k. Which line contains a subtle bug that causes incorrect counts for subarrays starting at index 0?

medium

A. Line 7: if prefix_sum - k in prefix_counts (wrong condition)

B. Line 5: prefix_sum += num (incorrect accumulation)

C. Line 3: prefix_counts = {} (missing initialization with {0:1})

D. Line 9: prefix_counts[prefix_sum] = prefix_counts.get(prefix_sum, 0) + 1 (incorrect update)

Solution

1. Step 1: Identify initialization of prefix_counts

   prefix_counts must start with {0:1} to count subarrays starting at index 0 correctly.

2. Step 2: Check other lines

   Accumulation, condition, and update lines are correct; only initialization is missing the base case.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Missing {0:1} causes missed counts for subarrays from start [OK]

Hint: Always initialize prefix_counts with {0:1} to handle subarrays from index 0 [OK]

Common Mistakes:

• Not initializing prefix_counts with {0:1}
• Misplacing prefix_sum updates
• Incorrect condition checks

5. What is the time complexity of the optimal bucket sort approach for finding the top k frequent elements in an array of size n with u unique elements?

medium

A. O(n + u) since building frequency map and buckets takes linear time

B. O(n log n) due to sorting the frequency map keys

C. O(u * log u) because sorting unique elements is required

D. O(n) because frequency counting and bucket filling are linear in n

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies requires iterating over n elements -> O(n)

2. Step 2: Analyze bucket filling and result collection

   Filling buckets and collecting top k elements is O(n) since total frequencies sum to n, plus O(u) for iterating unique elements.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Complexity is O(n + u), which is linear since u ≤ n [OK]

Hint: Frequency counting + bucket filling is linear [OK]

Common Mistakes:

• Assuming sorting unique keys is needed
• Confusing n with u in complexity
• Ignoring that bucket iteration is linear in total elements