Start learning free

GO · SLIDING WINDOW

Two Pointers Technique in Go, explained

What the sliding window is

Many array problems ask about a subarray: a run of consecutive elements such as nums[3:7]. The obvious way to search is to try every start and every end, and to add up the elements each time. That costs O(n²) pairs of positions, or O(n³) if you re-add every element for every pair.

The sliding window technique, a form of the two pointers technique, avoids most of that work. You keep two indices, one at each end of the current window, and a small piece of state describing what is inside, such as its sum. When the window moves one step, you update the state by adding the element that entered and removing the element that left. You never rebuild it from scratch, and the whole scan costs O(n).

The technique fits problems that ask for a contiguous range that is the longest, the shortest, or the first one satisfying a condition: a sum, a number of distinct values, or "no repeated values". It does not fit when the order of elements is irrelevant, or when the condition can't be maintained as the window moves.

Fixed-size windows

The simplest case has a window of constant length k. To find the largest sum of k consecutive numbers, compute the sum of the first window once, then slide: each step adds the new element on the right and subtracts the element that falls off on the left.

func maxWindowSum(nums []int, k int) int {
    if k <= 0 || k > len(nums) {
        return 0
    }
    sum := 0
    for i := 0; i < k; i++ {
        sum += nums[i]
    }
    best := sum
    for i := k; i < len(nums); i++ {
        sum += nums[i] - nums[i-k]
        best = max(best, sum)
    }
    return best
}

For nums = []int{2, 1, 5, 1, 3, 2} and k = 3, the windows have sums 8, 7, 9 and 6, so the function returns 9. Each element is added once and subtracted once, which gives O(n) time and O(1) extra space.

Variable-size windows

Most interview problems have a window whose size depends on a condition. The pattern uses two indices, here left and right:

  1. Move right forward one position at a time, adding nums[right] to the state.
  2. While the window breaks the condition (or, for "shortest" problems, while it satisfies it), move left forward, removing nums[left] from the state.
  3. Record the answer whenever the window is in the state the problem cares about.

Here is a shortest-subarray example with positive numbers: the length of the shortest subarray whose sum is at least target.

func shortestAtLeast(nums []int, target int) int {
    best := len(nums) + 1
    left, sum := 0, 0
    for right := 0; right < len(nums); right++ {
        sum += nums[right]
        for sum >= target {
            best = min(best, right-left+1)
            sum -= nums[left]
            left++
        }
    }
    if best == len(nums)+1 {
        return 0
    }
    return best
}

With nums = []int{2, 3, 1, 2, 4, 3} and target = 7 it returns 2, the window [4, 3]. With nums = []int{1, 1, 1} and target = 10 no window ever reaches the target, so it returns 0.

The nested loops look quadratic, but they are not. right moves forward n times in total, and left only ever moves forward, so it also moves at most n times. The inner loop's total work over the whole run is therefore at most n steps, and the algorithm is O(n). This is the reasoning to repeat for every sliding window solution you write.

Why positive numbers matter

The shrinking step relies on one fact: removing an element from the left makes the sum smaller (or equal), and adding one on the right makes it larger. That is only true when the numbers are non-negative. With negative numbers, shrinking can increase the sum and growing can decrease it, so the window can't decide which end to move, and other techniques, such as prefix sums with a map, take over. In this chapter the arrays hold positive or non-negative numbers, or the condition is about counts of values, which the window can maintain no matter the sign.

Go details that matter here

  • Use indices, not slices, for the window. Writing w := nums[left:right+1] is cheap because it shares the backing array and copies nothing, but it doesn't help you maintain a sum. Two integers left and right are all the window needs.
  • There is no while. Go has only for. A loop with just a condition, for sum >= target {, plays the role of while, and it is the usual way to write the shrinking step.
  • Check bounds first in a combined condition. In for last < len(nums) && sum+nums[last] <= S, the && stops evaluating as soon as its left side is false, so nums[last] is never read past the end. Reversing the two parts would panic with an index out of range error.
  • Counts live in a map. When the state is "how many times each value appears", use a map[int]int. Reading a missing key gives 0, so freq[v]++ works for a new value, and delete(freq, v) removes a value whose count reached zero so that len(freq) is the number of distinct values. A map[int]struct{} works as a set when you only need to know whether a value is present.
  • Built-in min and max. Since Go 1.21 they are part of the language, so best = max(best, sum) needs no helper function.
  • Integer sums can overflow. An int is 64 bits here and wraps around silently, which is rarely a problem for these tasks but worth remembering with very large values.

The lessons that follow

The next problems in this chapter all use the same skeleton with different state:

  • the longest subarray with sum at most S: state is a sum, the window grows while the sum stays within the limit;
  • the longest subarray with at most K distinct integers: state is a frequency map, and the window shrinks while the map has too many keys;
  • the longest subarray without repeated values: state is a set of the values inside the window;
  • a subarray with a given sum: state is a running sum, and the window shrinks while it exceeds the target.

For each one, ask three questions before writing code: what does the window hold, what does adding an element on the right change, and what does removing an element on the left change. The answers become the body of the two loops.

Key takeaways

  • A sliding window keeps two indices and incremental state, so each element is processed a constant number of times.
  • Fixed-size windows add one element and remove one per step; variable-size windows grow on the right and shrink on the left according to a condition.
  • The nested loops are still O(n) because neither index ever moves backwards.
  • The simple shrink-on-condition logic needs non-negative numbers; with negatives a different method is needed.
  • In Go, for cond {} replaces while, a map holds counts or a set, and bound checks go first in && conditions.
Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
Start learning free