Decisions and loops

A program that only runs top to bottom can do very little. Two things change that: choosing between paths, and repeating a step. Between them they account for nearly every line you will write in these problems.

Choosing: if and else#

if (n < 0) {
    return -1;
} else if (n == 0) {
    return 0;
} else {
    return 1;
}

if (n < 0) {
    return -1;
} else if (n == 0) {
    return 0;
} else {
    return 1;
}

if (n < 0) {
    return -1;
} else if (n == 0) {
    return 0;
} else {
    return 1;
}

if n < 0:
    return -1
elif n == 0:
    return 0
else:
    return 1

Python marks blocks with indentation instead of braces, and spells else if as elif. Otherwise the four are the same.

Handle the odd cases first and return early. An empty array, a zero, a single element: check for them at the top of the function and return. What is left below is the normal case, with one less thing to worry about.

Repeating a known number of times: for#

for (int i = 0; i < numsSize; i++) {
    total += nums[i];
}

for (int i = 0; i < (int) nums.size(); i++) {
    total += nums[i];
}
// Or, when you need the value and not the position:
for (int x : nums) {
    total += x;
}

for (int i = 0; i < nums.length; i++) {
    total += nums[i];
}
// Or, when you need the value and not the position:
for (int x : nums) {
    total += x;
}

for i in range(len(nums)):
    total += nums[i]
# Or, when you need the value and not the position:
for x in nums:
    total += x
# Or, when you need both:
for i, x in enumerate(nums):
    ...

Read for (int i = 0; i < n; i++) as: start at 0, keep going while i is below n, add one each time. So i takes the values 0, 1, ..., n - 1, which are exactly the valid positions of an array of length n. Python's range(n) gives the same numbers.

Repeating until something happens: while#

When you do not know in advance how many steps there are, use while:

int count = 0;
while (n > 0) {
    n /= 10;
    count++;
}

int count = 0;
while (n > 0) {
    n /= 10;
    count++;
}

int count = 0;
while (n > 0) {
    n /= 10;
    count++;
}

count = 0
while n > 0:
    n //= 10
    count += 1

Every while needs something inside it that moves towards the end. Here n shrinks each time. If nothing changes, the loop never stops, and the judge reports Time limit exceeded rather than an error.

Leaving early: break and continue#

• break leaves the loop entirely. Use it when you have found what you were looking for.
• continue skips the rest of this round and starts the next. Use it to ignore values you do not care about.

Often the neatest option is simply return from inside the loop the moment the answer is known.

Off by one#

The single most common bug in loops is being one step out: stopping one early, or reading one past the end.

• Positions run from 0 to length - 1. i <= n reads nums[n], which does not exist. In Java and Python that crashes; in C and C++ it quietly reads whatever memory comes next.
• When comparing each element with the next, stop at n - 1: for (i = 0; i < n - 1; i++) then compare nums[i] with nums[i + 1].
• Walking backwards: for (i = n - 1; i >= 0; i--) in the C family, for i in range(n - 1, -1, -1) in Python.

When unsure, check the two ends by hand: what does i equal on the first round, and on the last?

Loops inside loops, and what they cost#

A loop inside a loop runs its inside n × n times. For n = 1,000 that is a million steps, which is fine. For n = 100,000, the size many problems allow, it is ten billion, which no judge will wait for.

A rough guide for these problems is that the judge can do something like a hundred million simple steps a second. So:

Most of the later lessons are, one way or another, about replacing a loop inside a loop with something that does one pass. That starts with Hash maps for lookups, but it needs these basics first.

Try it#

Best time to buy a stock has an obvious answer with a loop inside a loop, and a better one with a single loop that remembers the cheapest price so far. Write the obvious one first, check it with Run, then see if you can find the single pass.