Count the work your method does
The constraints at the end of every statement tell you how much work the answer is allowed to do.
Count the basic steps your method takes on the biggest input. Two nested loops over n elements do about n²/2 steps. Sorting does about n log n. A loop that halves a range runs about log₂ n times. Keep every variable: a grid has R × C cells, and a graph has V vertices and E edges.
Count the hidden loops too. In Python, list.index, slicing and in on a list each scan the list, so calling one inside a loop multiplies the work by n. Building a string with += in a loop can copy the whole string every time.
The program below counts the pairs with a given sum in a sorted list two ways. Both find 500 pairs. The nested loops check 499,500 pairs and the two-pointer scan checks 500.
def pair_checks(nums, target):
checks = found = 0
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
checks += 1
if nums[i] + nums[j] == target:
found += 1
return found, checks
def two_pointer_checks(nums, target): # nums is sorted with distinct values
checks = found = 0
left, right = 0, len(nums) - 1
while left < right:
checks += 1
total = nums[left] + nums[right]
if total == target:
found += 1
left += 1
right -= 1
elif total < target:
left += 1
else:
right -= 1
return found, checks
nums = list(range(1000))
print("nested loops: %d pairs, %d checks" % pair_checks(nums, 999))
print("two pointers: %d pairs, %d checks" % two_pointer_checks(nums, 999))nested loops: 500 pairs, 499500 checks two pointers: 500 pairs, 500 checks
Compare it with the time limit
A rough budget: C++ does around 10⁸ simple operations a second, and a plain Python loop is 10 to 100 times slower. The real speed depends on the judge and the operation, but the estimate is good enough to throw ideas out.
With n = 10⁵, an O(n²) method needs about 10¹⁰ steps, which is over a minute of C++ against a one- or two-second limit. An O(n log n) method needs about 1.7 × 10⁶ steps and finishes instantly.
When the estimate lands close to the limit, constant factors decide it: plain arrays instead of hash maps in the inner loop, reading the input in one go, and in Python, built-in functions instead of hand-written loops.
Match the input size to a method
For a one- or two-second limit in a compiled language, the largest n usually points at one of these. Read each line as the slowest method that still fits.
n ≤ 10: O(n!), such as trying every permutation.
n ≤ 20: O(2ⁿ × n), such as trying every subset or a bitmask DP.
n ≤ 500: O(n³), such as three nested loops or Floyd-Warshall.
n ≤ 5,000: O(n²), such as a DP over pairs of indices.
n ≤ 10⁶: O(n log n) or O(n), such as sorting, a heap, prefix sums or two pointers.
n up to 10¹⁸: O(log n), such as binary search or fast exponentiation. Here n is a number, not the length of a list.
Check memory and recursion depth
In Python, move one line down the list when you’re close: an O(n²) loop over n = 5,000 is 25 million iterations, and that takes seconds. Several variables multiply, too. A 1,000 × 1,000 grid has 10⁶ cells, so one BFS over it is fine and comparing every pair of cells is not.
Memory limits are in megabytes. In C++, 10⁶ 64-bit integers take 8 MB. A Python list of 10⁶ integers stores a pointer to an integer object per entry and can take several times that. A 10⁴ × 10⁴ table has 10⁸ cells, 400 MB at 4 bytes each, which is over most limits. If each row only needs the previous one, keep two rows.
Recursion uses memory as well. A recursive DFS on a path of 10⁵ vertices goes 10⁵ calls deep, past Python’s default limit of 1,000 frames, and it can overflow the C++ stack on some judges. Use an explicit stack, or check the depth before you choose recursion.