Recognising a Pattern from Wording and Constraints
20 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)Good solvers do not start by coding. They read the limits and the wording, and they match them to a pattern they already know.
Read the limit before the story
An input limit is the largest size a problem allows, such as n at most 100000. It decides which solutions can finish in time: about 10 million simple steps is a safe budget in Python.
A problem with n up to 20 and one with n up to 100000 need very different ideas. The limit tells you how many steps each item may cost.
BUDGET = 10**7 # simple steps a Python solution can afford
def fits(n, steps): return steps(n) <= BUDGET
print(fits(10**5, lambda n: n * n))print(fits(10**5, lambda n: n * 17))print(fits(20, lambda n: 2 ** n))Example 1 · From limit to allowed cost
limits = [20, 1000, 10**5, 10**9]for n in limits: if n <= 20: kind = "2**n is fine" elif n <= 1000: kind = "n*n is fine" elif n <= 10**6: kind = "n log n is fine" else: kind = "need log n or maths" print(n, kind)20 2**n is fine 1000 n*n is fine 100000 n log n is fine 1000000000 need log n or maths
What this code does
- The limit is turned into the heaviest cost that still finishes.
- Real judges differ, so treat the table as a guide and not a law.
Checking every pair of 100000 items needs 10 billion steps, so it fails. Sorting-like work, about n times 17 steps, fits easily.
Words in the statement point to a pattern
A pattern is a reusable way of solving a whole family of problems, such as two pointers or a sliding window. Recognising it from the wording saves you from inventing a solution from nothing.
Statements repeat the same phrases: sorted, consecutive, every arrangement, smallest value that works. Each phrase usually points to one family of solutions.
CLUES = { "sorted": "binary search or two pointers", "consecutive": "sliding window or prefix sums", "every arrangement": "backtracking", "smallest value that works": "binary search on the answer", "appears twice": "XOR or a set",}
def suggest(text): return [idea for clue, idea in CLUES.items() if clue in text]
print(suggest("Find the smallest value that works for sorted slots"))Example 2 · Clue words on real statements
CLUES = { "sorted": "binary search or two pointers", "consecutive": "sliding window or prefix sums", "every arrangement": "backtracking", "smallest value that works": "binary search on the answer",}
statements = [ "largest total of k consecutive days", "print every arrangement of the tickets", "smallest value that works for D days",]for text in statements: hits = [idea for clue, idea in CLUES.items() if clue in text] print(text, "->", hits)largest total of k consecutive days -> ['sliding window or prefix sums'] print every arrangement of the tickets -> ['backtracking'] smallest value that works for D days -> ['binary search on the answer']
What this code does
- Each statement matches exactly one clue.
- The clue does not solve the problem. It tells you which template to try first.
Example 3 · Brute force, then a window
days = [2, 1, 5, 1, 3, 2, 9]k = 3
brute = max(sum(days[i:i + k]) for i in range(len(days) - k + 1))
window = sum(days[:k])best = windowfor i in range(k, len(days)): window += days[i] - days[i - k] best = max(best, window)
print(brute, best)14 14
What this code does
- Brute force adds k numbers for every start, about n times k steps.
- The window adds one number and removes one, so the whole pass takes about n steps.
The function lists every idea whose clue appears in the text. A real statement may match more than one, and you pick using the limits.
Sorted input and the cost of the first idea
Brute force means trying every possibility. It is simple to get right and shows exactly what a faster solution must still produce, so write it first or at least describe it.
Your first idea is often brute force. Compare its cost with the limit, then ask what the order of the data lets you skip.
def pairs_brute(prices, x): count = 0 for i in range(len(prices)): for j in range(i + 1, len(prices)): if prices[i] + prices[j] <= x: count += 1 return count
print(pairs_brute([1, 2, 3, 4, 5], 6))Example 4 · Brute force, then two pointers
prices = sorted([5, 1, 4, 2, 3])x = 6
brute = sum(1 for i in range(5) for j in range(i + 1, 5) if prices[i] + prices[j] <= x)
i, j, fast = 0, len(prices) - 1, 0while i < j: if prices[i] + prices[j] <= x: fast += j - i i += 1 else: j -= 1
print(brute, fast)6 6
What this code does
- Both ways print the same count, but the pointer version never looks at a pair twice.
- Sorting costs n log n once, then the pass is linear. Extra space is only the sorted list.
Two loops cost about n times n steps. If the prices are sorted, two pointers can count the same pairs in one pass.
Next step
Check your understanding
10 quick questions