Sum of Elements Between K1 and K2 Smallest (Sum Strictly Between Two Order Statistics)

• Order statistics – the K-th smallest element is the element at rank K when the array is sorted.
• Target band – elements strictly between the K1-th and K2-th smallest, i.e., ranks K1+1 to K2-1.
• Heap approach – a max-heap of size K2 keeps the K2 smallest; pop the top (K2-th smallest), then pop and sum until K1 remain.
• Sort approach – sort once and sum the slice from index K1 to K2-2 (zero-based), O(n log n).
• Complexity – heap: O(n log K2) time, O(K2) space; sort: O(n log n) time, O(1) extra.

What is the problem?

Given an array and two values K1 and K2 (K1 < K2), find the sum of all elements whose rank is strictly between K1 and K2 when sorted. Both the K1-th and K2-th smallest are excluded.

Example: array = [1, 3, 12, 5, 15, 11], K1 = 3, K2 = 6. Sorted: [1, 3, 5, 11, 12, 15]. Elements at ranks 4 and 5 (11 and 12) are the target. Sum = 23.

How do you solve it with sorting?

package com.bank.service;

import java.util.Arrays;

public class MidTierAnalyzer {

    public static long sumBetween(int[] balances, int k1, int k2) {
        Arrays.sort(balances);
        long sum = 0;
        // Sum elements at indices k1 to k2-2 (0-based)
        for (int i = k1; i < k2 - 1; i++) {
            sum += balances[i];
        }
        return sum;
    }

    public static void main(String[] args) {
        int[] balances = {1, 3, 12, 5, 15, 11};
        System.out.println("Sum between K1=3 and K2=6: " + sumBetween(balances, 3, 6));
    }
}

Sum between K1=3 and K2=6: 23

How do you solve it with a max-heap?

import java.util.Collections;
import java.util.PriorityQueue;

public static long sumBetweenHeap(int[] balances, int k1, int k2) {
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    for (int b : balances) {
        maxHeap.offer(b);
        if (maxHeap.size() > k2) maxHeap.poll(); // keep only k2 smallest
    }
    // maxHeap now holds the k2 smallest, root = k2-th smallest
    maxHeap.poll(); // discard k2-th smallest (upper exclusion)
    long sum = 0;
    while (maxHeap.size() > k1) {
        sum += maxHeap.poll(); // sum ranks k1+1 to k2-1
    }
    return sum;
}

How do the two approaches compare?

| Feature | Sort approach | Heap approach |
|---|---|---|
| Time | O(n log n) | O(n log K2) |
| Space | O(1) extra (in-place sort) | O(K2) |
| Better when | K2 close to n | K2 much smaller than n |
| Simplicity | simpler code | more steps |

What are edge cases?

- K2 - K1 <= 1: no elements strictly between, sum is 0.
- K1 = 0: elements from rank 1 to K2-1.
- Duplicate values: duplicates can span the boundary; be careful to count by rank, not by value.

What are common mistakes?

// Wrong: including the endpoints
for (int i = k1 - 1; i < k2; i++) sum += sorted[i]; // includes both endpoints!

// Correct: strictly between
for (int i = k1; i < k2 - 1; i++) sum += sorted[i]; // excludes both endpoints

What should a senior engineer know?

The correctness crux is the strict exclusions at both ends. In the heap approach, one pop discards the upper bound and stopping at K1 remaining discards the lower bound. In the sort approach, the index arithmetic (K1 to K2-2 zero-based) handles both exclusions.

For large-scale banking data, the heap approach scales better because K2 is often much smaller than the total number of accounts.

What are common interview follow-up questions?

• How would you find the K-th smallest element without sorting the entire array? (Quickselect)
• What if K1 and K2 are given as percentiles instead of ranks?
• How would you handle the sum with BigDecimal for monetary amounts?