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.
Move from brute-force thinking to an efficient approach using array strategy.
You are given two integer arrays, nums1 and nums2, both of length n, along with a positive integer k.
For each index i from 0 to n - 1, perform the following:
j where nums1[j] is less than nums1[i].k values of nums2[j] at these indices to maximize the total sum.Return an array answer of size n, where answer[i] represents the result for the corresponding index i.
Example 1:
Input: nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2
Output: [80,30,0,80,50]
Explanation:
i = 0: Select the 2 largest values from nums2 at indices [1, 2, 4] where nums1[j] < nums1[0], resulting in 50 + 30 = 80.i = 1: Select the 2 largest values from nums2 at index [2] where nums1[j] < nums1[1], resulting in 30.i = 2: No indices satisfy nums1[j] < nums1[2], resulting in 0.i = 3: Select the 2 largest values from nums2 at indices [0, 1, 2, 4] where nums1[j] < nums1[3], resulting in 50 + 30 = 80.i = 4: Select the 2 largest values from nums2 at indices [1, 2] where nums1[j] < nums1[4], resulting in 30 + 20 = 50.Example 2:
Input: nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1
Output: [0,0,0,0]
Explanation:
Since all elements in nums1 are equal, no indices satisfy the condition nums1[j] < nums1[i] for any i, resulting in 0 for all positions.
Constraints:
n == nums1.length == nums2.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 1061 <= k <= nProblem summary: You are given two integer arrays, nums1 and nums2, both of length n, along with a positive integer k. For each index i from 0 to n - 1, perform the following: Find all indices j where nums1[j] is less than nums1[i]. Choose at most k values of nums2[j] at these indices to maximize the total sum. Return an array answer of size n, where answer[i] represents the result for the corresponding index i.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array
[4,2,1,5,3] [10,20,30,40,50] 2
[2,2,2,2] [3,1,2,3] 1
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3478: Choose K Elements With Maximum Sum
class Solution {
public long[] findMaxSum(int[] nums1, int[] nums2, int k) {
int n = nums1.length;
int[][] arr = new int[n][0];
for (int i = 0; i < n; ++i) {
arr[i] = new int[] {nums1[i], i};
}
Arrays.sort(arr, (a, b) -> a[0] - b[0]);
PriorityQueue<Integer> pq = new PriorityQueue<>();
long s = 0;
long[] ans = new long[n];
int j = 0;
for (int h = 0; h < n; ++h) {
int x = arr[h][0], i = arr[h][1];
while (j < h && arr[j][0] < x) {
int y = nums2[arr[j][1]];
pq.offer(y);
s += y;
if (pq.size() > k) {
s -= pq.poll();
}
++j;
}
ans[i] = s;
}
return ans;
}
}
// Accepted solution for LeetCode #3478: Choose K Elements With Maximum Sum
func findMaxSum(nums1 []int, nums2 []int, k int) []int64 {
n := len(nums1)
arr := make([][2]int, n)
for i, x := range nums1 {
arr[i] = [2]int{x, i}
}
ans := make([]int64, n)
sort.Slice(arr, func(i, j int) bool { return arr[i][0] < arr[j][0] })
pq := hp{}
var s int64
j := 0
for h, e := range arr {
x, i := e[0], e[1]
for j < h && arr[j][0] < x {
y := nums2[arr[j][1]]
heap.Push(&pq, y)
s += int64(y)
if pq.Len() > k {
s -= int64(heap.Pop(&pq).(int))
}
j++
}
ans[i] = s
}
return ans
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}
# Accepted solution for LeetCode #3478: Choose K Elements With Maximum Sum
class Solution:
def findMaxSum(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
arr = [(x, i) for i, x in enumerate(nums1)]
arr.sort()
pq = []
s = j = 0
n = len(arr)
ans = [0] * n
for h, (x, i) in enumerate(arr):
while j < h and arr[j][0] < x:
y = nums2[arr[j][1]]
heappush(pq, y)
s += y
if len(pq) > k:
s -= heappop(pq)
j += 1
ans[i] = s
return ans
// Accepted solution for LeetCode #3478: Choose K Elements With Maximum Sum
// Rust example auto-generated from java 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 (java):
// // Accepted solution for LeetCode #3478: Choose K Elements With Maximum Sum
// class Solution {
// public long[] findMaxSum(int[] nums1, int[] nums2, int k) {
// int n = nums1.length;
// int[][] arr = new int[n][0];
// for (int i = 0; i < n; ++i) {
// arr[i] = new int[] {nums1[i], i};
// }
// Arrays.sort(arr, (a, b) -> a[0] - b[0]);
// PriorityQueue<Integer> pq = new PriorityQueue<>();
// long s = 0;
// long[] ans = new long[n];
// int j = 0;
// for (int h = 0; h < n; ++h) {
// int x = arr[h][0], i = arr[h][1];
// while (j < h && arr[j][0] < x) {
// int y = nums2[arr[j][1]];
// pq.offer(y);
// s += y;
// if (pq.size() > k) {
// s -= pq.poll();
// }
// ++j;
// }
// ans[i] = s;
// }
// return ans;
// }
// }
// Accepted solution for LeetCode #3478: Choose K Elements With Maximum Sum
function findMaxSum(nums1: number[], nums2: number[], k: number): number[] {
const n = nums1.length;
const arr = nums1.map((x, i) => [x, i]).sort((a, b) => a[0] - b[0]);
const pq = new MinPriorityQueue<number>();
let [s, j] = [0, 0];
const ans: number[] = Array(k).fill(0);
for (let h = 0; h < n; ++h) {
const [x, i] = arr[h];
while (j < h && arr[j][0] < x) {
const y = nums2[arr[j++][1]];
pq.enqueue(y);
s += y;
if (pq.size() > k) {
s -= pq.dequeue();
}
}
ans[i] = s;
}
return ans;
}
Use this to step through a reusable interview workflow for this problem.
Two nested loops check every pair or subarray. The outer loop fixes a starting point, the inner loop extends or searches. For n elements this gives up to n²/2 operations. No extra space, but the quadratic time is prohibitive for large inputs.
Most array problems have an O(n²) brute force (nested loops) and an O(n) optimal (single pass with clever state tracking). The key is identifying what information to maintain as you scan: a running max, a prefix sum, a hash map of seen values, or two pointers.
Review these before coding to avoid predictable interview regressions.
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.