Approach

1. Count frequencies f[x] of original values and find mx = max(nums). Allocate arrays up to mx + k to allow targets beyond mx.
2. Build prefix sums pre so pre[i] = total count of original values ≤ i (fast range counts).
3. For each target t in a reasonable range (e.g., from min(nums) to mx + k), compute L = t−k and R = t+k clamped to the original value domain.
4. Let tot = count of originals in [L, R] via prefix sums; adj = tot − f[t] are elements convertible to t.
5. The achievable frequency at t is f[t] + min(numOperations, adj). Take the maximum over all t.

Notes

Time O(n + mx + k), space O(mx + k). If the value range is large/sparse, you can compress coordinates or use a difference-array sweep over [min(nums), max(nums)] to compute coverage counts.

Reference Solution

func maxFrequency(nums []int, k int, numOperations int) int {
    mx := nums[0]
    for _, x := range nums {
        if x > mx {
            mx = x
        }
    }
    n := mx + k + 2
    f := make([]int, n)
    for _, x := range nums {
        f[x]++
    }
    pre := make([]int, n)
    pre[0] = f[0]
    for i := 1; i < n; i++ {
        pre[i] = pre[i-1] + f[i]
    }
    ans := 0
    for t := 0; t < n; t++ {
        if f[t] == 0 && numOperations == 0 {
            continue
        }
        l := t - k
        if l < 0 {
            l = 0
        }
        r := t + k
        if r > n-1 {
            r = n - 1
        }
        tot := pre[r]
        if l > 0 {
            tot -= pre[l-1]
        }
        adj := tot - f[t]
        val := f[t] + min(numOperations, adj)
        if val > ans {
            ans = val
        }
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Approach

1. Initialize X = 0.
2. Each operation is 3 characters long; the middle character (op[1]) is either '+' or '-'.
3. Add +1 to X if op[1] == '+', otherwise add -1.
4. Return X after processing all operations.

Notes

O(n) time, O(1) space. Prefix vs postfix doesn't matter because we only care about the side effect. Using op[1] is safe since operations are always length 3.

Reference Solution

func finalValueAfterOperations(operations []string) int {
    X := 0
    values := map[byte]int{'+': 1, '-': -1}
    for _, op := range operations {
        X += values[op[1]]
    }
    return X
}

Approach

1. Build rows iteratively from top to bottom.
2. For row i (0-indexed), create an array of length i+1.
3. Set row[0] = row[i] = 1. For 1 ≤ j < i, set row[j] = prev[j-1] + prev[j].
4. Append each row to the answer and return after numRows iterations.

Notes

Time O(n^2) and space O(n^2) over all rows. You can also compute each row using binomial coefficients, but the DP-from-previous-row method is straightforward.

Reference Solution

package main

import "fmt"

func generate(numRows int) [][]int {
	ans := [][]int{{1}}

	for i := 1; i < numRows; i++ {
		row := make([]int, i+1)
		row[0], row[i] = 1, 1
		for j := 1; j < i; j++ {
			row[j] = ans[i-1][j-1] + ans[i-1][j]
		}
		ans = append(ans, row)
	}

	return ans
}

Approach

1. Model the count as f(n) = f(n-1) + f(n-2) with f(0)=1, f(1)=1.
2. Use iterative DP carrying only the last two values (O(1) space).
3. Initialize a = f(0) = 1 and b = f(1) = 1; for i from 2 to n set a, b = b, a + b.
4. Handle n <= 1 by returning 1; after the loop, return b as f(n).

Notes

Time O(n), space O(1). Alternative solutions include recursion with memoization (also O(n) time, O(n) space) and matrix exponentiation/fast doubling for O(log n) time.

Reference Solution

func climbStairs(n int) int {
    if n <= 1 {
        return 1 // f(0)=1, f(1)=1
    }
    a, b := 1, 1 // a=f(0), b=f(1)
    for i := 2; i <= n; i++ {
        a, b = b, a+b // now b=f(i)
    }
    return b // f(n)
}

Approach

1. Let dp[i] represent the total energy collected starting from magician i.
2. Compute dp[i] = energy[i] + dp[i + k] if i + k is within bounds; otherwise dp[i] = energy[i].
3. Iterate backward (from right to left) so dp[i + k] is already known.
4. Track the maximum value among all dp[i] as the final result.

Notes

Initialize result with a very small number (-1 << 31) to handle negative-only arrays. This ensures the first computed value replaces it correctly.

Reference Solution

func maximumEnergy(energy []int, k int) int {
    n := len(energy)
    dp := make([]int, n)
    result := -1 << 31 // start with the smallest 32-bit integer

    for i := n - 1; i >= 0; i-- {
        next := 0
        if i + k < n {
            next = dp[i + k]
        }
        dp[i] = energy[i] + next
        if dp[i] > result {
            result = dp[i]
        }
    }
    return result
}