Approach

1. View the array as being partitioned into maximal smooth descent runs where consecutive prices differ by exactly 1.
2. Traverse prices from left to right while keeping a variable length that stores the length of the current descent run ending at i.
3. If prices[i] == prices[i-1] - 1, extend the current run by incrementing length; otherwise, reset length back to 1 for the new single-day run.
4. For each i, add length to the answer, since exactly length smooth descent subarrays end at index i, implicitly summing k * (k + 1) / 2 for every run.

Notes

This one-pass O(n) solution simply accumulates the contribution of each maximal smooth descent run without explicitly computing k * (k + 1) / 2; using int64 for the answer is important because the total number of periods can be up to n * (n + 1) / 2.

Reference Solution

func getDescentPeriods(prices []int) int64 {
    n := len(prices)
    if n == 0 {
        return 0
    }

    var ans int64 = 1   // the first day alone is always a valid period
    var length int64 = 1 // length of the current smooth descent run ending at i

    for i := 1; i < n; i++ {
        if prices[i] == prices[i-1]-1 {
            length++
        } else {
            length = 1
        }
        ans += length
    }

    return ans
}

Approach

1. Compute the total sum of all battery capacities.
2. Sort the batteries in ascending order to process the largest ones last.
3. A very large battery may exceed the average available energy per computer (totalEnergy / n). Such a battery could power one computer on its own without sharing, so it is removed from the pooled energy: subtract it from totalEnergy and decrease n by 1.
4. Continue removing these oversized batteries until none exceed the current average.
5. Once only balanced batteries remain, the maximum uniform running time is totalEnergy / n.

Notes

The key insight is that extremely large batteries distort the shareable average. Removing them effectively assigns them to their own computers, allowing the remaining energy to be evenly distributed among the remaining machines. This greedy method yields the optimal solution.

Reference Solution

import "sort"


func maxRunTime(n int, batteries []int) int64 {
    var totalEnergy int64 = 0
    for _, b := range batteries {
        totalEnergy += int64(b)
    }

    sort.Ints(batteries)

    for i := len(batteries) - 1; i >= 0; i-- {
        if int64(batteries[i]) > totalEnergy/int64(n) {
            totalEnergy -= int64(batteries[i])
            n--
        } else {
            break
        }
    }

    return totalEnergy / int64(n)
}

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
}