Go Guide

Core patterns · Lesson 15 of 62 · about 50 min

Arrays & matrices

Kadane's algorithm and its variations for maximum subarrays, matrix traversal and rotation, and in-place tricks like the Dutch national flag and the reversal rotation.

Go by Example: Arrays ↗Go by Example: Slices ↗
On this page · 8 sections
  1. 01Maximum subarray: from O(n³) to O(n)
  2. 02Kadane variations
  3. 03In-place tricks in one dimension
  4. 04Matrices
  5. 05Complexity
  6. 06Summary
  7. 07Check your understanding
  8. 08Practice in Go

Maximum subarray: from O(n³) to O(n)#

"Find the contiguous subarray with the largest sum." The obvious solution tries every start and every end and adds up the middle: O(n³). Keeping a running sum for each start brings it to O(n²). Kadane's insight brings it to O(n):

The best subarray ending at index i is either nums[i] alone, or nums[i] added to the best subarray ending at i-1.

If the best sum ending at i-1 is negative, adding it can only hurt, so you start fresh. Keep the best value seen anywhere as the answer.

Go
cur, best := nums[0], nums[0]
for _, n := range nums[1:] {
	cur = max(n, cur+n) // extend, or start over at n
	best = max(best, cur)
}

Trace [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

ncur + nn alonecur = maxbest
-2-2-2
1-111 (start over)1
-3-2-3-21
4244 (start over)4
-13-134
25255
16166
-51-516
45456

The answer is 6, from [4, -1, 2, 1].

Kadane is really a tiny dynamic program: cur is "the best answer for subarrays that end exactly here", and each step depends only on the previous one. You will meet this shape again in Module 4.

Kadane variations#

The same "best ending here" idea adapts to several famous problems. This program solves four of them and returns the subarray's boundaries, not just the sum:

kadane.go
Go
package main
 
import "fmt"
 
// maxSubarray returns the best sum and the half-open range [start, end) that achieves it.
func maxSubarray(nums []int) (best, start, end int) {
	cur, curStart := nums[0], 0
	best, start, end = nums[0], 0, 1
	for i := 1; i < len(nums); i++ {
		if cur+nums[i] < nums[i] {
			cur, curStart = nums[i], i // start over
		} else {
			cur += nums[i]
		}
		if cur > best {
			best, start, end = cur, curStart, i+1
		}
	}
	return best, start, end
}
 
// maxProduct tracks the largest AND smallest product ending here,
// because a negative number swaps them.
func maxProduct(nums []int) int {
	hi, lo, best := nums[0], nums[0], nums[0]
	for _, n := range nums[1:] {
		if n < 0 {
			hi, lo = lo, hi
		}
		hi = max(n, hi*n)
		lo = min(n, lo*n)
		best = max(best, hi)
	}
	return best
}
 
// maxCircular allows the subarray to wrap from the end back to the start.
func maxCircular(nums []int) int {
	total := 0
	curMax, bestMax := 0, nums[0]
	curMin, bestMin := 0, nums[0]
	for _, n := range nums {
		total += n
		curMax = max(n, curMax+n)
		bestMax = max(bestMax, curMax)
		curMin = min(n, curMin+n)
		bestMin = min(bestMin, curMin)
	}
	if bestMax < 0 {
		return bestMax // all negative: removing everything would leave an empty subarray
	}
	return max(bestMax, total-bestMin)
}
 
// maxProfit is Kadane in disguise: keep the cheapest price so far.
func maxProfit(prices []int) int {
	minPrice, best := prices[0], 0
	for _, p := range prices[1:] {
		best = max(best, p-minPrice)
		minPrice = min(minPrice, p)
	}
	return best
}
 
func main() {
	nums := []int{-2, 1, -3, 4, -1, 2, 1, -5, 4}
	best, s, e := maxSubarray(nums)
	fmt.Println("max subarray:", best, nums[s:e])
	fmt.Println("all negative:", fmt.Sprint(maxSubarray([]int{-3, -1, -2})))
 
	fmt.Println("max product:", maxProduct([]int{2, 3, -2, 4}), maxProduct([]int{-2, 3, -4}))
	fmt.Println("circular:", maxCircular([]int{5, -3, 5}), maxCircular([]int{-3, -2, -3}))
	fmt.Println("stock profit:", maxProfit([]int{7, 1, 5, 3, 6, 4}))
}
Output
max subarray: 6 [4 -1 2 1]
all negative: -1 1 2
max product: 6 24
circular: 10 -2
stock profit: 5

Read the variations side by side:

ProblemState kept per indexTwist
maximum subarraybest sum ending herestart over when the old run is negative
maximum productbest and worst product ending herea negative number swaps best and worst
circular subarraybest and worst suma wrapping answer = total minus the worst middle piece
buy and sell stock oncecheapest price so farprofit if we sell today

In-place tricks in one dimension#

Rotate by k with three reversals

Rotating [1 2 3 4 5 6 7] right by 3 should give [5 6 7 1 2 3 4]. Copying into a new slice is easy; doing it in place with O(1) memory uses a neat trick:

stepslice
start1 2 3 4 5 6 7
reverse all7 6 5 4 3 2 1
reverse first k = 35 6 7 4 3 2 1
reverse the rest5 6 7 1 2 3 4

Dutch national flag (sort three values in one pass)

To sort a slice holding only 0s, 1s and 2s, keep three regions: [0, low) holds 0s, [low, mid) holds 1s, (high, end] holds 2s, and [mid, high] is still unknown. Look at nums[mid]:

  • 0: swap it to low, advance both low and mid;
  • 1: it is already in the middle region, advance mid;
  • 2: swap it to high and shrink high, but do not advance mid, because the value swapped in has not been examined yet.
inplace.go
Go
package main
 
import (
	"fmt"
	"slices"
)
 
func rotate(nums []int, k int) {
	k %= len(nums)
	slices.Reverse(nums)
	slices.Reverse(nums[:k])
	slices.Reverse(nums[k:])
}
 
func sortColors(nums []int) {
	low, mid, high := 0, 0, len(nums)-1
	for mid <= high {
		switch nums[mid] {
		case 0:
			nums[low], nums[mid] = nums[mid], nums[low]
			low++
			mid++
		case 1:
			mid++
		case 2:
			nums[mid], nums[high] = nums[high], nums[mid]
			high-- // nums[mid] is new and unexamined, so mid stays
		}
		fmt.Println("  ", nums, "low", low, "mid", mid, "high", high)
	}
}
 
// moveZeroes keeps the order of non-zero values: a fast/slow pointer pass.
func moveZeroes(nums []int) {
	slow := 0
	for _, n := range nums {
		if n != 0 {
			nums[slow] = n
			slow++
		}
	}
	clear(nums[slow:])
}
 
func main() {
	a := []int{1, 2, 3, 4, 5, 6, 7}
	rotate(a, 3)
	fmt.Println("rotate right by 3:", a)
 
	colors := []int{2, 0, 2, 1, 1, 0}
	fmt.Println("sort colors:")
	sortColors(colors)
 
	z := []int{0, 1, 0, 3, 12}
	moveZeroes(z)
	fmt.Println("move zeroes:", z)
}
Output
rotate right by 3: [5 6 7 1 2 3 4]
sort colors:
   [0 0 2 1 1 2] low 0 mid 0 high 4
   [0 0 2 1 1 2] low 1 mid 1 high 4
   [0 0 2 1 1 2] low 2 mid 2 high 4
   [0 0 1 1 2 2] low 2 mid 2 high 3
   [0 0 1 1 2 2] low 2 mid 3 high 3
   [0 0 1 1 2 2] low 2 mid 4 high 3
move zeroes: [1 3 12 0 0]

clear (Go 1.21) sets every element of a slice to its zero value, here zeroing the tail in one call.

Matrices#

In Go a matrix is usually a slice of slices, [][]int, indexed grid[row][col]. Three habits prevent most bugs:

  • name the sizes once: rows, cols := len(grid), len(grid[0]);
  • keep row in the first index and column in the second, always;
  • check bounds before indexing neighbors: r >= 0 && r < rows && c >= 0 && c < cols.

Rotate 90° clockwise, in place

Transpose (swap m[i][j] with m[j][i] above the diagonal), then reverse each row:

1 2 3      1 4 7      7 4 1
4 5 6  ->  2 5 8  ->  8 5 2
7 8 9      3 6 9      9 6 3
 start   transpose  reverse rows

Spiral order

Keep four boundaries, top, bottom, left, right. Walk right along the top row, then down the right column, then left along the bottom, then up the left column, shrinking the matching boundary after each side. Stop when the boundaries cross.

Searching a sorted matrix

If every row and every column is sorted, start in the top-right corner. If the value there is too big, the whole column below is too big too: move left. If it is too small, the whole row to the left is too small: move down. Each step removes a row or a column, so the search is O(rows + cols).

matrix.go
Go
package main
 
import "fmt"
 
func rotate(m [][]int) {
	n := len(m)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			m[i][j], m[j][i] = m[j][i], m[i][j]
		}
	}
	for _, row := range m {
		for l, r := 0, n-1; l < r; l, r = l+1, r-1 {
			row[l], row[r] = row[r], row[l]
		}
	}
}
 
func spiral(m [][]int) []int {
	var out []int
	top, bottom, left, right := 0, len(m)-1, 0, len(m[0])-1
	for top <= bottom && left <= right {
		for c := left; c <= right; c++ {
			out = append(out, m[top][c])
		}
		top++
		for r := top; r <= bottom; r++ {
			out = append(out, m[r][right])
		}
		right--
		if top <= bottom {
			for c := right; c >= left; c-- {
				out = append(out, m[bottom][c])
			}
			bottom--
		}
		if left <= right {
			for r := bottom; r >= top; r-- {
				out = append(out, m[r][left])
			}
			left++
		}
	}
	return out
}
 
func searchSorted(m [][]int, target int) (int, int, int) {
	r, c, steps := 0, len(m[0])-1, 0
	for r < len(m) && c >= 0 {
		steps++
		switch v := m[r][c]; {
		case v == target:
			return r, c, steps
		case v > target:
			c-- // everything below in this column is even bigger
		default:
			r++ // everything left in this row is even smaller
		}
	}
	return -1, -1, steps
}
 
func main() {
	m := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
	rotate(m)
	fmt.Println("rotated:", m)
 
	fmt.Println("spiral:", spiral([][]int{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}))
 
	sorted := [][]int{
		{1, 4, 7, 11},
		{2, 5, 8, 12},
		{3, 6, 9, 16},
		{10, 13, 14, 17},
	}
	fmt.Println(searchSorted(sorted, 9))
	fmt.Println(searchSorted(sorted, 15))
}
Output
rotated: [[7 4 1] [8 5 2] [9 6 3]]
spiral: [1 2 3 4 8 12 11 10 9 5 6 7]
2 2 4
-1 -1 5

Finding 9 took 4 steps and proving 15 is missing took 5, against 16 cells for a full scan. The spiral's two if checks matter for non-square matrices: without them, a single remaining row or column would be printed twice.

Complexity#

ProblemTimeExtra space
maximum subarray / product / circularO(n)O(1)
rotate slice by kO(n)O(1)
Dutch national flag, move zeroesO(n)O(1)
rotate matrixO(n²)O(1)
spiral orderO(rows · cols)O(1) besides the output
search sorted matrixO(rows + cols)O(1)

Summary#

  • Kadane: the best subarray ending here either extends the previous one or starts over. One pass, O(1) memory.
  • Products need both a maximum and a minimum; circular arrays use total minus the minimum subarray.
  • Three reversals rotate a slice in place; three pointers sort three values in one pass.
  • Matrices: fix the [row][col] convention, name the sizes, check bounds before indexing.
  • A sorted matrix is searched from a corner where one direction grows and the other shrinks.

Check your understanding

Answer before scrolling back up. If you miss one, reread the matching section, then try again.

  1. Q1.In Kadane's algorithm, when do you start a new subarray at index i?

  2. Q2.Why does maximum product subarray track both the maximum and the minimum product ending at each index?

  3. Q3.The maximum circular subarray sum is the larger of the normal Kadane answer and:

  4. Q4.Rotating an n×n matrix 90° clockwise in place can be done by:

  5. Q5.Rotating a slice right by k with three reversals reverses:

Practice in Go

Write a table test first, then the solution. On LeetCode, choose Go as the language. Open a hint only after 15 minutes stuck.

Finished this lesson?

Mark it done to track your progress. It is saved in this browser only.