LeetCode #3762 — HARD

Minimum Operations to Equalize Subarrays

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

The Problem

Problem Statement

You are given an integer array nums and an integer k.

In one operation, you can increase or decrease any element of nums by exactly k.

You are also given a 2D integer array queries, where each queries[i] = [l_i, r_i].

For each query, find the minimum number of operations required to make all elements in the subarray nums[l_i..r_i] equal. If it is impossible, the answer for that query is -1.

Return an array ans, where ans[i] is the answer for the i^th query.

Example 1:

Input: nums = [1,4,7], k = 3, queries = [[0,1],[0,2]]

Output: [1,2]

Explanation:

One optimal set of operations:

`i`	`[l_i, r_i]`	`nums[l_i..r_i]`	Possibility	Operations	Final `nums[l_i..r_i]`	`ans[i]`
0	[0, 1]	[1, 4]	Yes	`nums[0] + k = 1 + 3 = 4 = nums[1]`	[4, 4]	1
1	[0, 2]	[1, 4, 7]	Yes	`nums[0] + k = 1 + 3 = 4 = nums[1] nums[2] - k = 7 - 3 = 4 = nums[1]`	[4, 4, 4]	2

Thus, ans = [1, 2].

Example 2:

Input: nums = [1,2,4], k = 2, queries = [[0,2],[0,0],[1,2]]

Output: [-1,0,1]

Explanation:

One optimal set of operations:

`i`	`[l_i, r_i]`	`nums[l_i..r_i]`	Possibility	Operations	Final `nums[l_i..r_i]`	`ans[i]`
0	[0, 2]	[1, 2, 4]	No	-	[1, 2, 4]	-1
1	[0, 0]	[1]	Yes	Already equal	[1]	0
2	[1, 2]	[2, 4]	Yes	`nums[1] + k = 2 + 2 = 4 = nums[2]`	[4, 4]	1

Thus, ans = [-1, 0, 1].

Constraints:

1 <= n == nums.length <= 4 × 10⁴
1 <= nums[i] <= 10⁹
1 <= k <= 10⁹
1 <= queries.length <= 4 × 10⁴
queries[i] = [l_i, r_i]
0 <= l_i <= r_i <= n - 1

Step 01

Brute Force Baseline

Problem summary: You are given an integer array nums and an integer k. In one operation, you can increase or decrease any element of nums by exactly k. You are also given a 2D integer array queries, where each queries[i] = [li, ri]. For each query, find the minimum number of operations required to make all elements in the subarray nums[li..ri] equal. If it is impossible, the answer for that query is -1. Return an array ans, where ans[i] is the answer for the ith query.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Math · Binary Search · Segment Tree

Example 1

[1,4,7]
3
[[0,1],[0,2]]

Example 2

[1,2,4]
2
[[0,2],[0,0],[1,2]]

Step 02

Core Insight

What unlocks the optimal approach

To make all elements in a subarray equal, they must all share the same remainder when divided by <code>k</code>.
The problem is equivalent to making <code>nums[i] / k</code> equal for all elements in the subarray. The minimum operations to achieve this is to make them all equal to the median of these <code>nums[i] / k</code> values.
To handle many queries efficiently, pre-process the array. Group elements by their remainder mod <code>k</code>. For each group, we need a data structure to find the median and sum of absolute differences for any given range.
A Persistent Segment Tree can answer range median and range sum queries in logarithmic time, making it suitable for this problem.

Interview move: turn each hint into an invariant you can check after every iteration/recursion step.

Step 03

Algorithm Walkthrough

Iteration Checklist

Define state (indices, window, stack, map, DP cell, or recursion frame).
Apply one transition step and update the invariant.
Record answer candidate when condition is met.
Continue until all input is consumed.

Use the first example testcase as your mental trace to verify each transition.

Step 04

Edge Cases

Minimum Input

Single element / shortest valid input

Validate boundary behavior before entering the main loop or recursion.

Duplicates & Repeats

Repeated values / repeated states

Decide whether duplicates should be merged, skipped, or counted explicitly.

Extreme Constraints

Largest constraint values

Re-check complexity target against constraints to avoid time-limit issues.

Invalid / Corner Shape

Empty collections, zeros, or disconnected structures

Handle special-case structure before the core algorithm path.

Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3762: Minimum Operations to Equalize Subarrays
// Auto-generated Java example from go.
class Solution {
    public void exampleSolution() {
    }
}
// Reference (go):
// // Accepted solution for LeetCode #3762: Minimum Operations to Equalize Subarrays
// package main
// 
// import (
// 	"runtime/debug"
// 	"slices"
// 	"sort"
// )
// 
// // https://space.bilibili.com/206214
// // 有大量指针的题目，关闭 GC 更快
// func init() { debug.SetGCPercent(-1) }
// 
// type node struct {
// 	lo, ro   *node
// 	l, r     int
// 	cnt, sum int
// }
// 
// func (o *node) maintain() {
// 	o.cnt = o.lo.cnt + o.ro.cnt
// 	o.sum = o.lo.sum + o.ro.sum
// }
// 
// func build(l, r int) *node {
// 	o := &node{l: l, r: r}
// 	if l == r {
// 		return o
// 	}
// 	mid := (l + r) / 2
// 	o.lo = build(l, mid)
// 	o.ro = build(mid+1, r)
// 	return o
// }
// 
// // 在线段树的位置 i 添加 val
// // 注意这里传的不是指针，会把 node 复制一份，而这正好是我们需要的
// func (o node) add(i, val int) *node {
// 	if o.l == o.r {
// 		o.cnt++
// 		o.sum += val
// 		return &o
// 	}
// 	mid := (o.l + o.r) / 2
// 	if i <= mid {
// 		o.lo = o.lo.add(i, val)
// 	} else {
// 		o.ro = o.ro.add(i, val)
// 	}
// 	o.maintain()
// 	return &o
// }
// 
// // 查询 old 和 o 对应子数组的第 k 小，有多少个数小于第 k 小，这些数的元素和是多少
// func (o *node) query(old *node, k int) (int, int, int) {
// 	if o.l == o.r {
// 		return o.l, 0, 0
// 	}
// 	cntL := o.lo.cnt - old.lo.cnt
// 	if k <= cntL {
// 		return o.lo.query(old.lo, k)
// 	}
// 	i, c, s := o.ro.query(old.ro, k-cntL)
// 	sumL := o.lo.sum - old.lo.sum
// 	return i, cntL + c, sumL + s
// }
// 
// func minOperations(nums []int, k int, queries [][]int) []int64 {
// 	n := len(nums)
// 	left := make([]int, n)
// 	for i := 1; i < n; i++ {
// 		if nums[i]%k != nums[i-1]%k {
// 			left[i] = i
// 		} else {
// 			left[i] = left[i-1]
// 		}
// 	}
// 
// 	// 准备离散化
// 	sorted := slices.Clone(nums)
// 	slices.Sort(sorted)
// 	sorted = slices.Compact(sorted)
// 
// 	t := make([]*node, n+1)
// 	t[0] = build(0, len(sorted)-1)
// 	for i, x := range nums {
// 		j := sort.SearchInts(sorted, x) // 离散化
// 		t[i+1] = t[i].add(j, x)         // 构建可持久化线段树
// 	}
// 
// 	ans := make([]int64, len(queries))
// 	for qi, q := range queries {
// 		l, r := q[0], q[1]
// 		if left[r] > l { // 无解
// 			ans[qi] = -1
// 			continue
// 		}
// 
// 		r++ // 改成左闭右开，方便计算
// 
// 		// 计算区间中位数
// 		sz := r - l
// 		i, cntLeft, sumLeft := t[r].query(t[l], sz/2+1)
// 		median := sorted[i] // 离散化后的值 -> 原始值
// 
// 		// 计算区间所有元素到中位数的距离和
// 		total := t[r].sum - t[l].sum                 // 区间元素和
// 		sum := median*cntLeft - sumLeft              // 蓝色面积
// 		sum += total - sumLeft - median*(sz-cntLeft) // 绿色面积
// 		ans[qi] = int64(sum / k)                     // 操作次数 = 距离和 / k
// 	}
// 	return ans
// }

// Accepted solution for LeetCode #3762: Minimum Operations to Equalize Subarrays
package main

import (
	"runtime/debug"
	"slices"
	"sort"
)

// https://space.bilibili.com/206214
// 有大量指针的题目，关闭 GC 更快
func init() { debug.SetGCPercent(-1) }

type node struct {
	lo, ro   *node
	l, r     int
	cnt, sum int
}

func (o *node) maintain() {
	o.cnt = o.lo.cnt + o.ro.cnt
	o.sum = o.lo.sum + o.ro.sum
}

func build(l, r int) *node {
	o := &node{l: l, r: r}
	if l == r {
		return o
	}
	mid := (l + r) / 2
	o.lo = build(l, mid)
	o.ro = build(mid+1, r)
	return o
}

// 在线段树的位置 i 添加 val
// 注意这里传的不是指针，会把 node 复制一份，而这正好是我们需要的
func (o node) add(i, val int) *node {
	if o.l == o.r {
		o.cnt++
		o.sum += val
		return &o
	}
	mid := (o.l + o.r) / 2
	if i <= mid {
		o.lo = o.lo.add(i, val)
	} else {
		o.ro = o.ro.add(i, val)
	}
	o.maintain()
	return &o
}

// 查询 old 和 o 对应子数组的第 k 小，有多少个数小于第 k 小，这些数的元素和是多少
func (o *node) query(old *node, k int) (int, int, int) {
	if o.l == o.r {
		return o.l, 0, 0
	}
	cntL := o.lo.cnt - old.lo.cnt
	if k <= cntL {
		return o.lo.query(old.lo, k)
	}
	i, c, s := o.ro.query(old.ro, k-cntL)
	sumL := o.lo.sum - old.lo.sum
	return i, cntL + c, sumL + s
}

func minOperations(nums []int, k int, queries [][]int) []int64 {
	n := len(nums)
	left := make([]int, n)
	for i := 1; i < n; i++ {
		if nums[i]%k != nums[i-1]%k {
			left[i] = i
		} else {
			left[i] = left[i-1]
		}
	}

	// 准备离散化
	sorted := slices.Clone(nums)
	slices.Sort(sorted)
	sorted = slices.Compact(sorted)

	t := make([]*node, n+1)
	t[0] = build(0, len(sorted)-1)
	for i, x := range nums {
		j := sort.SearchInts(sorted, x) // 离散化
		t[i+1] = t[i].add(j, x)         // 构建可持久化线段树
	}

	ans := make([]int64, len(queries))
	for qi, q := range queries {
		l, r := q[0], q[1]
		if left[r] > l { // 无解
			ans[qi] = -1
			continue
		}

		r++ // 改成左闭右开，方便计算

		// 计算区间中位数
		sz := r - l
		i, cntLeft, sumLeft := t[r].query(t[l], sz/2+1)
		median := sorted[i] // 离散化后的值 -> 原始值

		// 计算区间所有元素到中位数的距离和
		total := t[r].sum - t[l].sum                 // 区间元素和
		sum := median*cntLeft - sumLeft              // 蓝色面积
		sum += total - sumLeft - median*(sz-cntLeft) // 绿色面积
		ans[qi] = int64(sum / k)                     // 操作次数 = 距离和 / k
	}
	return ans
}

# Accepted solution for LeetCode #3762: Minimum Operations to Equalize Subarrays
#
# @lc app=leetcode id=3762 lang=python3
#
# [3762] Minimum Operations to Equalize Subarrays
#

# @lc code=start
from bisect import bisect_right

class Solution:
    def minOperations(self, nums: List[int], k: int, queries: List[List[int]]) -> List[int]:
        n = len(nums)
        quots = [x // k for x in nums]
        rems = [x % k for x in nums]
        
        # Precompute validity check
        # A subarray is valid if all elements have the same remainder modulo k.
        # We can use a prefix sum array to check this in O(1).
        # mismatch[i] = 1 if nums[i] % k != nums[i-1] % k else 0
        mismatch = [0] * n
        for i in range(1, n):
            if rems[i] != rems[i-1]:
                mismatch[i] = 1
        
        mismatch_pref = [0] * (n + 1)
        for i in range(n):
            mismatch_pref[i+1] = mismatch_pref[i] + mismatch[i]
            
        # Merge Sort Tree Construction
        # tree[v] stores a sorted list of quotients for the range covered by node v
        # pref[v] stores the prefix sums of that sorted list
        self.tree = [[] for _ in range(4 * n)]
        self.pref = [[] for _ in range(4 * n)]
        
        def build(node, start, end):
            if start == end:
                self.tree[node] = [quots[start]]
                self.pref[node] = [0, quots[start]]
                return
            
            mid = (start + end) // 2
            build(2 * node, start, mid)
            build(2 * node + 1, mid + 1, end)
            
            # Merge two sorted arrays
            left_arr = self.tree[2 * node]
            right_arr = self.tree[2 * node + 1]
            merged = []
            i = j = 0
            while i < len(left_arr) and j < len(right_arr):
                if left_arr[i] < right_arr[j]:
                    merged.append(left_arr[i])
                    i += 1
                else:
                    merged.append(right_arr[j])
                    j += 1
            merged.extend(left_arr[i:])
            merged.extend(right_arr[j:])
            
            self.tree[node] = merged
            
            # Build prefix sums for the merged array
            p = [0] * (len(merged) + 1)
            curr = 0
            for idx, val in enumerate(merged):
                curr += val
                p[idx+1] = curr
            self.pref[node] = p

        build(1, 0, n - 1)
        
        # Helper to get count of numbers <= val in range [L, R]
        def query_count(node, start, end, L, R, val):
            if R < start or end < L:
                return 0
            if L <= start and end <= R:
                return bisect_right(self.tree[node], val)
            mid = (start + end) // 2
            return query_count(2 * node, start, mid, L, R, val) + \
                   query_count(2 * node + 1, mid + 1, end, L, R, val)

        # Helper to find the k-th smallest number (0-indexed rank) in range [L, R]
        # We binary search on the answer space (min_val to max_val)
        min_val = min(quots)
        max_val = max(quots)
        
        def get_quantile(L, R, rank):
            low = min_val
            high = max_val
            ans = high
            
            while low <= high:
                mid = (low + high) // 2
                # count how many numbers are <= mid inside [L, R]
                c = query_count(1, 0, n - 1, L, R, mid)
                if c > rank:
                    ans = mid
                    high = mid - 1
                else:
                    low = mid + 1
            return ans

        # Helper to get sum and count of numbers <= val in range [L, R]
        def query_sum_count(node, start, end, L, R, val):
            if R < start or end < L:
                return 0, 0
            if L <= start and end <= R:
                idx = bisect_right(self.tree[node], val)
                return self.pref[node][idx], idx
            
            mid = (start + end) // 2
            s1, c1 = query_sum_count(2 * node, start, mid, L, R, val)
            s2, c2 = query_sum_count(2 * node + 1, mid + 1, end, L, R, val)
            return s1 + s2, c1 + c2

        ans = []
        for l, r in queries:
            # Check validity
            # If mismatch_pref[r+1] - mismatch_pref[l+1] > 0, it means there's a mismatch inside
            # Actually, mismatch at index i compares i and i-1.
            # For range [l, r], we need to check mismatches at l+1, l+2, ..., r.
            # So we look at mismatch_pref[r+1] - mismatch_pref[l+1].
            # If l == r, valid automatically.
            if l < r and (mismatch_pref[r+1] - mismatch_pref[l+1] > 0):
                ans.append(-1)
                continue
            
            # Find Median
            count = r - l + 1
            median_rank = count // 2  # 0-indexed rank of median
            median_val = get_quantile(l, r, median_rank)
            
            # Calculate Cost
            # Cost = sum(|x - median|) for x in range
            #      = (count_less * median - sum_less) + (sum_greater - count_greater * median)
            # where less includes equal to median for simplicity in splitting, 
            # but strictly speaking |x - median| is 0 for x=median so it doesn't matter which side equal goes.
            
            sum_less, count_less = query_sum_count(1, 0, n - 1, l, r, median_val)
            
            # Total sum of the range [l, r]
            # We can get total sum by querying with infinity or just reuse the logic
            # Actually, sum_greater = total_sum - sum_less
            # count_greater = total_count - count_less
            
            # To get total sum efficiently, we can use a standard prefix sum array for quots
            # let's build it on the fly or precompute it. Precomputing is better.
            
            # But wait, query_sum_count gives us sum of subset.
            # We need total sum of quots[l...r].
            # Let's add a simple prefix sum array for quots.
            pass 

        # Add simple prefix sum for quots
        quot_pref = [0] * (n + 1)
        for i in range(n):
            quot_pref[i+1] = quot_pref[i] + quots[i]

        ans = []
        for l, r in queries:
            if l < r and (mismatch_pref[r+1] - mismatch_pref[l+1] > 0):
                ans.append(-1)
                continue
            
            count = r - l + 1
            median_rank = count // 2 
            median_val = get_quantile(l, r, median_rank)
            
            sum_le, cnt_le = query_sum_count(1, 0, n - 1, l, r, median_val)
            
            total_sum = quot_pref[r+1] - quot_pref[l]
            sum_gt = total_sum - sum_le
            cnt_gt = count - cnt_le
            
            cost = (cnt_le * median_val - sum_le) + (sum_gt - cnt_gt * median_val)
            ans.append(cost)
            
        return ans
# @lc code=end

// Accepted solution for LeetCode #3762: Minimum Operations to Equalize Subarrays
// Rust example auto-generated from go reference.
// Replace the signature and local types with the exact LeetCode harness for this problem.
impl Solution {
    pub fn rust_example() {
        // Port the logic from the reference block below.
    }
}

// Reference (go):
// // Accepted solution for LeetCode #3762: Minimum Operations to Equalize Subarrays
// package main
// 
// import (
// 	"runtime/debug"
// 	"slices"
// 	"sort"
// )
// 
// // https://space.bilibili.com/206214
// // 有大量指针的题目，关闭 GC 更快
// func init() { debug.SetGCPercent(-1) }
// 
// type node struct {
// 	lo, ro   *node
// 	l, r     int
// 	cnt, sum int
// }
// 
// func (o *node) maintain() {
// 	o.cnt = o.lo.cnt + o.ro.cnt
// 	o.sum = o.lo.sum + o.ro.sum
// }
// 
// func build(l, r int) *node {
// 	o := &node{l: l, r: r}
// 	if l == r {
// 		return o
// 	}
// 	mid := (l + r) / 2
// 	o.lo = build(l, mid)
// 	o.ro = build(mid+1, r)
// 	return o
// }
// 
// // 在线段树的位置 i 添加 val
// // 注意这里传的不是指针，会把 node 复制一份，而这正好是我们需要的
// func (o node) add(i, val int) *node {
// 	if o.l == o.r {
// 		o.cnt++
// 		o.sum += val
// 		return &o
// 	}
// 	mid := (o.l + o.r) / 2
// 	if i <= mid {
// 		o.lo = o.lo.add(i, val)
// 	} else {
// 		o.ro = o.ro.add(i, val)
// 	}
// 	o.maintain()
// 	return &o
// }
// 
// // 查询 old 和 o 对应子数组的第 k 小，有多少个数小于第 k 小，这些数的元素和是多少
// func (o *node) query(old *node, k int) (int, int, int) {
// 	if o.l == o.r {
// 		return o.l, 0, 0
// 	}
// 	cntL := o.lo.cnt - old.lo.cnt
// 	if k <= cntL {
// 		return o.lo.query(old.lo, k)
// 	}
// 	i, c, s := o.ro.query(old.ro, k-cntL)
// 	sumL := o.lo.sum - old.lo.sum
// 	return i, cntL + c, sumL + s
// }
// 
// func minOperations(nums []int, k int, queries [][]int) []int64 {
// 	n := len(nums)
// 	left := make([]int, n)
// 	for i := 1; i < n; i++ {
// 		if nums[i]%k != nums[i-1]%k {
// 			left[i] = i
// 		} else {
// 			left[i] = left[i-1]
// 		}
// 	}
// 
// 	// 准备离散化
// 	sorted := slices.Clone(nums)
// 	slices.Sort(sorted)
// 	sorted = slices.Compact(sorted)
// 
// 	t := make([]*node, n+1)
// 	t[0] = build(0, len(sorted)-1)
// 	for i, x := range nums {
// 		j := sort.SearchInts(sorted, x) // 离散化
// 		t[i+1] = t[i].add(j, x)         // 构建可持久化线段树
// 	}
// 
// 	ans := make([]int64, len(queries))
// 	for qi, q := range queries {
// 		l, r := q[0], q[1]
// 		if left[r] > l { // 无解
// 			ans[qi] = -1
// 			continue
// 		}
// 
// 		r++ // 改成左闭右开，方便计算
// 
// 		// 计算区间中位数
// 		sz := r - l
// 		i, cntLeft, sumLeft := t[r].query(t[l], sz/2+1)
// 		median := sorted[i] // 离散化后的值 -> 原始值
// 
// 		// 计算区间所有元素到中位数的距离和
// 		total := t[r].sum - t[l].sum                 // 区间元素和
// 		sum := median*cntLeft - sumLeft              // 蓝色面积
// 		sum += total - sumLeft - median*(sz-cntLeft) // 绿色面积
// 		ans[qi] = int64(sum / k)                     // 操作次数 = 距离和 / k
// 	}
// 	return ans
// }

// Accepted solution for LeetCode #3762: Minimum Operations to Equalize Subarrays
// Auto-generated TypeScript example from go.
function exampleSolution(): void {
}
// Reference (go):
// // Accepted solution for LeetCode #3762: Minimum Operations to Equalize Subarrays
// package main
// 
// import (
// 	"runtime/debug"
// 	"slices"
// 	"sort"
// )
// 
// // https://space.bilibili.com/206214
// // 有大量指针的题目，关闭 GC 更快
// func init() { debug.SetGCPercent(-1) }
// 
// type node struct {
// 	lo, ro   *node
// 	l, r     int
// 	cnt, sum int
// }
// 
// func (o *node) maintain() {
// 	o.cnt = o.lo.cnt + o.ro.cnt
// 	o.sum = o.lo.sum + o.ro.sum
// }
// 
// func build(l, r int) *node {
// 	o := &node{l: l, r: r}
// 	if l == r {
// 		return o
// 	}
// 	mid := (l + r) / 2
// 	o.lo = build(l, mid)
// 	o.ro = build(mid+1, r)
// 	return o
// }
// 
// // 在线段树的位置 i 添加 val
// // 注意这里传的不是指针，会把 node 复制一份，而这正好是我们需要的
// func (o node) add(i, val int) *node {
// 	if o.l == o.r {
// 		o.cnt++
// 		o.sum += val
// 		return &o
// 	}
// 	mid := (o.l + o.r) / 2
// 	if i <= mid {
// 		o.lo = o.lo.add(i, val)
// 	} else {
// 		o.ro = o.ro.add(i, val)
// 	}
// 	o.maintain()
// 	return &o
// }
// 
// // 查询 old 和 o 对应子数组的第 k 小，有多少个数小于第 k 小，这些数的元素和是多少
// func (o *node) query(old *node, k int) (int, int, int) {
// 	if o.l == o.r {
// 		return o.l, 0, 0
// 	}
// 	cntL := o.lo.cnt - old.lo.cnt
// 	if k <= cntL {
// 		return o.lo.query(old.lo, k)
// 	}
// 	i, c, s := o.ro.query(old.ro, k-cntL)
// 	sumL := o.lo.sum - old.lo.sum
// 	return i, cntL + c, sumL + s
// }
// 
// func minOperations(nums []int, k int, queries [][]int) []int64 {
// 	n := len(nums)
// 	left := make([]int, n)
// 	for i := 1; i < n; i++ {
// 		if nums[i]%k != nums[i-1]%k {
// 			left[i] = i
// 		} else {
// 			left[i] = left[i-1]
// 		}
// 	}
// 
// 	// 准备离散化
// 	sorted := slices.Clone(nums)
// 	slices.Sort(sorted)
// 	sorted = slices.Compact(sorted)
// 
// 	t := make([]*node, n+1)
// 	t[0] = build(0, len(sorted)-1)
// 	for i, x := range nums {
// 		j := sort.SearchInts(sorted, x) // 离散化
// 		t[i+1] = t[i].add(j, x)         // 构建可持久化线段树
// 	}
// 
// 	ans := make([]int64, len(queries))
// 	for qi, q := range queries {
// 		l, r := q[0], q[1]
// 		if left[r] > l { // 无解
// 			ans[qi] = -1
// 			continue
// 		}
// 
// 		r++ // 改成左闭右开，方便计算
// 
// 		// 计算区间中位数
// 		sz := r - l
// 		i, cntLeft, sumLeft := t[r].query(t[l], sz/2+1)
// 		median := sorted[i] // 离散化后的值 -> 原始值
// 
// 		// 计算区间所有元素到中位数的距离和
// 		total := t[r].sum - t[l].sum                 // 区间元素和
// 		sum := median*cntLeft - sumLeft              // 蓝色面积
// 		sum += total - sumLeft - median*(sz-cntLeft) // 绿色面积
// 		ans[qi] = int64(sum / k)                     // 操作次数 = 距离和 / k
// 	}
// 	return ans
// }

Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Custom checkpoints (one per line)

Press Step or Run All to begin.

Step 07

Complexity Analysis

Time

O(log n)

Space

O(1)

Approach Breakdown

LINEAR SCAN

O(n) time

O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH

O(log n) time

O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.

Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Overflow in intermediate arithmetic

Wrong move: Temporary multiplications exceed integer bounds.

Usually fails on: Large inputs wrap around unexpectedly.

Fix: Use wider types, modular arithmetic, or rearranged operations.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.