🎓 A1Learner
🔍
0 of 93 lessons completed

DSA When You Are Stuck

Being stuck means the pattern a problem needs is not yet visible. A ladder of six moves turns being stuck into a procedure.

Shrink and draw the small case

The problem counts pairs of days whose bookings sum to a target. On four days, every pair fits in one small table with its sum marked.

days = [2, 5, 4, 3]
target = 7
for i in range(len(days)):
    for j in range(i + 1, len(days)):
        total = days[i] + days[j]
        mark = "HIT" if total == target else "-"
        print(i, j, days[i], "+", days[j], "=", total, mark)

Brute force the full input

The brute force checks every pair and counts its own checks. It is slow, but its answer is the truth the faster rungs must match.

def count_brute(nums, target):
    count = 0
    checks = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            checks += 1
            if nums[i] + nums[j] == target:
                count += 1
    return count, checks

print("pairs and checks:", count_brute([4, 2, 6, 2, 5, 1, 3, 2], 7))

Sort it and walk two pointers

Sorting the bookings loses the original day order, and pair counting never needed it. Two pointers then count the same pairs from the two ends.

def count_sorted(nums, target):
    a = sorted(nums)
    count = 0
    left, right = 0, len(a) - 1
    while left < right:
        s = a[left] + a[right]
        if s < target:
            left += 1
        elif s > target:
            right -= 1
        elif a[left] == a[right]:
            m = right - left + 1
            count += m * (m - 1) // 2
            break
        else:
            lc = 0
            while a[left + lc] == a[left]:
                lc += 1
            rc = 0
            while a[right - rc] == a[right]:
                rc += 1
            count += lc * rc
            left += lc
            right -= rc
    return count

nums = [4, 2, 6, 2, 5, 1, 3, 2]
print("sorted:", sorted(nums))
print("pairs:", count_sorted(nums, 7))

Example

def count_brute(nums, target):
    count = 0
    checks = 0
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            checks += 1
            if nums[i] + nums[j] == target:
                count += 1
    return count, checks

def count_sorted(nums, target):
    a = sorted(nums)
    count = 0
    left, right = 0, len(a) - 1
    while left < right:
        s = a[left] + a[right]
        if s < target:
            left += 1
        elif s > target:
            right -= 1
        elif a[left] == a[right]:
            m = right - left + 1
            count += m * (m - 1) // 2
            break
        else:
            lc = 0
            while a[left + lc] == a[left]:
                lc += 1
            rc = 0
            while a[right - rc] == a[right]:
                rc += 1
            count += lc * rc
            left += lc
            right -= rc
    return count

def count_hash(nums, target):
    seen = {}
    count = 0
    lookups = 0
    for x in nums:
        lookups += 1
        count += seen.get(target - x, 0)
        seen[x] = seen.get(x, 0) + 1
    return count, lookups

def count_split(nums, target):
    mid = len(nums) // 2
    left, right = nums[:mid], nums[mid:]
    total = count_brute(left, target)[0] + count_brute(right, target)[0]
    freq = {}
    for y in right:
        freq[y] = freq.get(y, 0) + 1
    for x in left:
        total += freq.get(target - x, 0)
    return total

small = [2, 5, 4, 3]
nums = [4, 2, 6, 2, 5, 1, 3, 2]
target = 7
print("rung 1 shrink:", count_brute(small, target), "on", small)
print("rung 2 draw: pair sums for the small case")
for i in range(len(small)):
    for j in range(i + 1, len(small)):
        total = small[i] + small[j]
        mark = "HIT" if total == target else "-"
        print("  ", i, j, small[i], "+", small[j], "=", total, mark)
print("rung 3 brute force:", count_brute(nums, target))
print("rung 4 sort it:", count_sorted(nums, target))
print("rung 5 hash it:", count_hash(nums, target))
print("rung 6 split it:", count_split(nums, target))

Key points

  • A ladder of six moves turns being stuck into a procedure.
  • Shrink the input when the full size hides the structure.
  • Draw the small case when indices and positions start to tangle.
  • Brute force it when a slow answer can verify a fast one.
  • Sort it when order matters more than the original positions.
  • Hash it when each element asks which value would complete it.
  • Split it when the answer combines answers from two halves.

In this example, one stuck problem climbs all six rungs in order. The problem counts pairs of booking days that sum to 7. Rung one shrank the input to four days and brute forced 2 pairs. Rung two drew every pair sum for that small case. Two pairs hit the target. Rung three brute forced the full list and found 5 pairs in 28 checks. Rung four sorted the list and counted 5 pairs with two pointers. Rung five hashed the values seen so far and counted 5 pairs in 8 lookups. Rung six split the list in half and combined the inside counts with the cross pairs. It also found 5. Four different routes agree on 5, so the answer is trusted. The hash rung is the one to code in the interview, at O(n) time and O(n) space.

Note

Climb one rung at a time and keep the answer each rung gives.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

Your draft keeps asking, for each value, which other value would complete it. Which rung fits that sign?