First array problems

Most array problems start the same way: walk the array once and keep a running answer. Sum it, count in it, find its largest value.

The tricky part is knowing when one walk is enough. This lesson's main problem, "is this array sorted?", looks like it needs every pair compared. It needs only the neighbours.

The linear scan: one pass, one running answer

A linear scan keeps one variable that holds the answer for the items seen so far. Each new item updates it.

┌────────────────────────────────────────────┐
│                                            │
│         arr      3    8    1    6          │
│                            ▲               │
│         total    3   11   12   18          │
│                                            │
└────────────────────────────────────────────┘

JavaPythonTypeScript

int sum(int[] arr) {
    int total = 0; // the sum of the items seen so far
    for (int x : arr) total += x;
    return total;
}

• The Python version is sum_array, because sum is a built-in. sum(arr) does the same loop for you.
• In Java, make total a long when the sum can pass about 2 × 10⁹.

Two of this lesson's problems are this loop with a different middle line:

Test odd numbers with != 0, not == 1. In Java and TypeScript, -3 % 2 is -1, so == 1 misses negative odd numbers. Python gives 1, but != 0 is right in all three.

Both read each item once and keep one number: O(n) time, O(1) extra space.

Read the problem

Ask these before you code:

• Equal neighbours? "Non-decreasing" allows them. [1, 2, 2, 3] is sorted.
• One item? Sorted. There is nothing to be out of order with.
• Negative values? Fine. The comparison does not care about the sign.
• Which direction? Increasing only. [3, 2, 1] is false.

n reaches 10⁶. One pass is 10⁶ steps, well inside the budget. A loop inside a loop would be about 5 × 10¹¹.

Brute force: compare every pair

Sorted means every value is at most every value after it. So check exactly that: for each i, compare arr[i] with every later value.

JavaPythonTypeScript

boolean isSorted(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] < arr[i]) return false;
        }
    }
    return true;
}

Count it out loud. The worst case is an array that is sorted, because the loops never stop early.

• The outer loop runs n times.
• The inner loop runs n − 1, then n − 2, and so on.
• That adds up to n × (n − 1) / 2, so O(n²).

For n = 10⁶, that is about 5 × 10¹¹ comparisons. Far too slow.

The key insight: neighbours are enough

If 2 ≤ 4 and 4 ≤ 7, then 2 ≤ 7. You never need to compare 2 with 7 directly. Order carries along the chain.

So an array is sorted when every value is at least the one right before it. One step down anywhere breaks it.

┌────────────────────────────────────────────┐
│                                            │
│                                 ▓▓         │
│                       ▓▓        ▓▓         │
│                       ▓▓   ▓▓   ▓▓         │
│             ▓▓   ▓▓   ▓▓   ▓▓   ▓▓         │
│        ▓▓   ▓▓   ▓▓   ▓▓   ▓▓   ▓▓         │
│        2    4    4    7    5    9          │
│                            ▲               │
│                        a step down         │
│                                            │
└────────────────────────────────────────────┘

The brute force repeats this work: it compares 2 with 7, 5 and 9, even though the neighbour checks already cover them.

Optimal: one pass over neighbours

1. Start at i = 1, so there is always a value before it.
2. If arr[i] is smaller than arr[i - 1], return false.
3. If the loop ends, every pair was in order. Return true.

The same example, the same step down:

JavaPythonTypeScript

boolean isSorted(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] < arr[i - 1]) return false; // a step down breaks the order
    }
    return true;
}

• Invariant: when the loop reaches i, everything before i is in order.
• Time: at most n − 1 comparisons, so O(n). Space: O(1).
• One item: the loop never runs, so the answer is true.

Side by side

The middle row works (in TypeScript, only with (a, b) => a - b). But it sorts the whole array to answer a yes-or-no question.

Reverse in place: two pointers

"Reverse an array" adds a rule: change the array itself, with no second array.

Use two pointers. left starts at the first item and right at the last. Swap them, then move both toward the middle.

┌───────────────────────────────────────────────────┐
│                                                   │
│   start     1   2   3   4   5                     │
│             ▲               ▲                     │
│           left            right    swap 1 and 5   │
│   pass 1    5   2   3   4   1                     │
│                 ▲       ▲          swap 2 and 4   │
│   pass 2    5   4   3   2   1                     │
│                     ▲              meet: stop     │
│                                                   │
└───────────────────────────────────────────────────┘

JavaPythonTypeScript

void reverseInPlace(int[] arr) {
    int left = 0;
    int right = arr.length - 1;
    while (left < right) {
        int temp = arr[left]; // swap the two ends
        arr[left] = arr[right];
        arr[right] = temp;
        left++;
        right--;
    }
}

• n / 2 swaps, so O(n) time and O(1) extra space.
• An odd length leaves the middle item where it is. One item or an empty array: the loop never runs.
• Java swaps through a temp variable. Python and TypeScript swap both values in one line.
• Each language has a built-in: Collections.reverse(list) in Java (not for int[]), arr.reverse() in Python and TypeScript. In an interview, write the loop.

How to spot this pattern

The linear scan template:

JavaPythonTypeScript

int answer = 0; // the answer for the items seen so far
for (int i = 0; i < arr.length; i++) {
    // update answer from arr[i], or stop early
}

You will meet two pointers again soon, for moving zeros and removing duplicates in the Arrays chapter.

take U forwardYouTube

Read more

• Array.prototype.reverse() on MDN, the in-place reverse
• More on lists in the Python tutorial, including list.reverse()
• Check if the Array is Sorted I on takeUforward, to solve it yourself

Next: counting with a hash map, to answer "how many times?" in one pass.