Math & Geometry

These problems are less about a data structure and more about careful reasoning on numbers and matrices: moving things in place, spotting repeating cycles and avoiding overflow. They reward drawing small examples by hand.

After this topic: You can manipulate matrices in place, use fast exponentiation, and detect cycles in numeric sequences.

Do these first: 2-D Dynamic Programming, Bit Manipulation

0 of 8 solved0%

Step 1 · Read the lesson

Bit Manipulation & Math

XOR tricks, bit counting, in-place matrix moves, fast exponentiation and digit-by-digit arithmetic.

Step 2 · Solve the problems in order

Try each one for about 20 minutes first. Problems with a Run code tab are checked right here. If you are stuck, open Nudge, think again, then Idea. Go skeleton only gives the function shape, and Reference solution is for comparing after you have tried. Tick the box when you could solve it again without help.

1.Rotate ImageMedium
A 90° rotation is two simpler moves combined.
Transpose the matrix (swap [i][j] with [j][i]), then reverse each row. Or rotate four cells at a time layer by layer.
Target: O(n²) time, O(1) space
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func rotate(matrix [][]int)
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// Rotate: rotate an n×n matrix 90° clockwise in place = transpose, then reverse every row. 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] } } }

2.Spiral MatrixMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func spiralOrder(matrix [][]int) []int

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.

// SpiralOrder: walk the outer ring, then shrink the four boundaries.
func SpiralOrder(m [][]int) []int {
	if len(m) == 0 {
		return nil
	}
	top, bottom, left, right := 0, len(m)-1, 0, len(m[0])-1
	var out []int
	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 { // a single remaining row must not be walked twice
			for c := right; c >= left; c-- {
				out = append(out, m[bottom][c])
			}
			bottom--
		}
		if left <= right { // same for a single remaining column
			for r := bottom; r >= top; r-- {
				out = append(out, m[r][left])
			}
			left++
		}
	}
	return out
}

3.Set Matrix ZeroesMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func setZeroes(matrix [][]int)

Tested with go test. Try it yourself first, then compare.

// SetZeroes zeroes the whole row and column of every 0, using O(1) extra memory: the first row and first column
// double as the "clear this row / column" markers. Two flags remember whether those two themselves need clearing.
func SetZeroes(m [][]int) {
	rows, cols := len(m), len(m[0])
	firstRow, firstCol := false, false
	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {
			if m[r][c] == 0 {
				if r == 0 {
					firstRow = true
				}
				if c == 0 {
					firstCol = true
				}
				m[r][0], m[0][c] = 0, 0 // mark the row and the column
			}
		}
	}
	for r := 1; r < rows; r++ {
		for c := 1; c < cols; c++ {
			if m[r][0] == 0 || m[0][c] == 0 {
				m[r][c] = 0
			}
		}
	}
	if firstRow {
		for c := 0; c < cols; c++ {
			m[0][c] = 0
		}
	}
	if firstCol {
		for r := 0; r < rows; r++ {
			m[r][0] = 0
		}
	}
}

4.Happy NumberEasy
The sequence either reaches 1 or loops forever. Where have you seen cycle detection?
Repeat sum-of-squares-of-digits; stop at 1 (happy) or when a value repeats (use a set or slow/fast pointers).
Target: O(log n) per step
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func isHappy(n int) bool
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// IsHappy: sum the squares of the digits repeatedly. Reaching 1 means happy; // the sequence is a linked list, so a repeat means a cycle (detected with slow and fast pointers). func IsHappy(n int) bool { step := func(x int) int { sum := 0 for ; x > 0; x /= 10 { d := x % 10 sum += d * d } return sum } slow, fast := n, step(n) for fast != 1 && slow != fast { slow = step(slow) fast = step(step(fast)) } return fast == 1 }
5.Plus OneEasy
Start from the last digit. When does the carry stop?
Walk from the end: a digit < 9 gets +1 and you are done; 9s become 0; if everything was 9 prepend a 1.
Target: O(n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func plusOne(digits []int) []int
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// PlusOne: add one to a number stored as a digit slice. func PlusOne(digits []int) []int { for i := len(digits) - 1; i >= 0; i-- { if digits[i] < 9 { digits[i]++ return digits // no carry left to pass on } digits[i] = 0 // 9 + 1 = 0, carry one position left } return append([]int{1}, digits...) // all nines: 999 -> 1000 }
6.Pow(x, n)Medium
x^n = (x^(n/2))². How many multiplications does that save? Handle negative n.
Fast exponentiation: recurse on n/2, square it, multiply by x if n is odd; for negative n invert x.
Target: O(log n) time
Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.
func myPow(x float64, n int) float64
Tested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.
// MyPow: fast exponentiation. x^n = (x^(n/2))^2, times x when n is odd. O(log n) multiplications. func MyPow(x float64, n int) float64 { if n < 0 { return 1 / MyPow(x, -n) } if n == 0 { return 1 } half := MyPow(x, n/2) if n%2 == 0 { return half * half } return half * half * x }

7.Multiply StringsMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

func multiply(num1 string, num2 string) string

Tested with go test. Try it yourself first, then compare. It is explained step by step on the Bit Manipulation & Math lesson page.

// Multiply: multiply two numbers given as strings, digit by digit like on paper.
// Digit i of a times digit j of b lands in result position i+j+1 (carry goes to i+j).
func Multiply(a, b string) string {
	if a == "0" || b == "0" {
		return "0"
	}
	res := make([]int, len(a)+len(b))
	for i := len(a) - 1; i >= 0; i-- {
		for j := len(b) - 1; j >= 0; j-- {
			sum := int(a[i]-'0')*int(b[j]-'0') + res[i+j+1]
			res[i+j+1] = sum % 10
			res[i+j] += sum / 10
		}
	}
	out := make([]byte, 0, len(res))
	for i, d := range res {
		if i == 0 && d == 0 {
			continue // strip the single possible leading zero
		}
		out = append(out, byte('0'+d))
	}
	return string(out)
}

8.Detect SquaresMedium

Types such as ListNode, TreeNode and Node are the standard ones for these problems. Define them yourself if you run the code locally.

type DetectSquares struct{}
func Constructor() DetectSquares
func (d *DetectSquares) Add(point []int)
func (d *DetectSquares) Count(point []int) int

Tested with go test. Try it yourself first, then compare.

// DetectSquares stores how many times each point was added. For a query point, every stored point on a diagonal
// (same distance in x and y, not zero) is a possible opposite corner; the other two corners must also exist,
// and the number of squares is the product of the three counts.
type DetectSquares struct{ count map[[2]int]int }

func NewDetectSquares() *DetectSquares { return &DetectSquares{count: map[[2]int]int{}} }

func (d *DetectSquares) Add(point []int) { d.count[[2]int{point[0], point[1]}]++ }

func (d *DetectSquares) Count(point []int) int {
	qx, qy := point[0], point[1]
	total := 0
	for p, n := range d.count {
		dx, dy := p[0]-qx, p[1]-qy
		if dx == 0 || abs(dx) != abs(dy) {
			continue // not a diagonal corner
		}
		total += n * d.count[[2]int{qx, p[1]}] * d.count[[2]int{p[0], qy}]
	}
	return total
}