🎓 A1Learner
🔍

DSA What Changes at the Hard Level

The hard level is where known patterns compose and an invariant carries the proof of correctness. Every problem gets attacked twice, once for correctness and once for the operation bound.

Two patterns compose in one problem

Sorting prepares the data and two pointers then scan it once. The composition finds the pair below.

nums = [8, 3, 5, 1, 9, 4]
ordered = sorted(nums)
print("sorted:", ordered)
left = 0
right = len(ordered) - 1
target = 12
while left < right:
    total = ordered[left] + ordered[right]
    if total == target:
        print("pair:", ordered[left], ordered[right])
        break
    if total < target:
        left += 1
    else:
        right -= 1

An invariant names what stays true

The binary search below keeps one promise at every step. The target, if present, always sits inside the current range.

nums = [2, 5, 8, 12, 16, 23]
target = 12
lo = 0
hi = len(nums) - 1
while lo <= hi:
    mid = (lo + hi) // 2
    print("range:", lo, hi, "value:", nums[mid])
    if nums[mid] == target:
        print("found at index:", mid)
        break
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1

Counts prove the bound

Operation counts compare two methods without any clock. The halving search needs far fewer comparisons than the full scan.

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
target = 13
linear = 0
for value in nums:
    linear += 1
    if value == target:
        break
lo = 0
hi = len(nums) - 1
binary = 0
while lo <= hi:
    mid = (lo + hi) // 2
    binary += 1
    if nums[mid] == target:
        break
    if nums[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print("linear comparisons:", linear)
print("binary comparisons:", binary)

Example

nums = [1, 4, 6, 8, 11, 15, 19, 22]
target = 26


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


def pointed(nums, target):
    left = 0
    right = len(nums) - 1
    steps = 0
    print("invariant: a valid pair, if one exists, lies between left and right")
    while left < right:
        steps += 1
        total = nums[left] + nums[right]
        print("step:", steps, "left:", left, "right:", right, "sum:", total)
        if total == target:
            return (nums[left], nums[right]), steps
        if total < target:
            left += 1
        else:
            right -= 1
    return None, steps


pair, checks = brute(nums, target)
print("brute pair:", pair, "checks:", checks)
pair, steps = pointed(nums, target)
print("pointer pair:", pair, "steps:", steps)

Key points

  • Composition means two or more known patterns solving one problem together.
  • An invariant is a statement that stays true at every step of an algorithm.
  • A stated invariant rules out wrong answers without testing them one by one.
  • The first attack finds a correct solution and names its invariant.
  • The second attack counts operations and proves the claimed bound.
  • The main change at this level is proof, not harder syntax.

In this example, a Beginner pair problem is solved again at the hard level. The brute force version checks pairs in order and uses thirteen checks. The two-pointer version states its invariant before the loop starts. Each printed step keeps that promise while the range shrinks. The pair 4 and 22 appears after two steps, and the counts carry the proof.

Note

The clock matters in interviews, but counts are the evidence used here.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A solution is correct but its cost is unproven. Which attack is still missing?