Balanced Subsequence Sums — Problem Statement & Solution Guide
Problem Description
Given an array of integers sequence of length n, identify all subsequences of length 9 that satisfy two specific structural conditions. First, the sum of the first 7 elements in the subsequence must be strictly equal to the sum of the last 7 elements in the subsequence. Note that the 5th element (the middle element) is included in both the first 7 and the last 7 elements. Second, the middle element (the 5th element of the subsequence) must be the maximum value among all 9 elements in that subsequence.
Return the total count of such valid subsequences. The order of elements in the subsequence must preserve their relative order from the original array, but they do not need to be contiguous.
For a subsequence of indices $i_1 < i_2 < \dots < i_9$, let the values be $v_1, v_2, \dots, v_9$. The conditions are:
1. $\sum_{k=1}^{7} v_k = \sum_{k=3}^{9} v_k$
2. $v_5 = \max(v_1, v_2, \dots, v_9)$
DSA Pattern Breakdown
DSA Pattern Breakdown
"Balanced Subsequence Sums"
WHY DOES IT MATTER?
Reducing a seemingly complex 7‑element equality to a simple two‑sum problem transforms an intractable combinatorial search into a classic hash‑based lookup, a pattern that appears in many interview questions such as 3‑sum, 4‑sum, and subarray sum problems.
OPTIMIZATION CHALLENGE
The critical insight is that the overlapping 5 elements cancel out, collapsing the 7‑element equality to a 2‑element equality. This reduces the dimensionality of the search space from 9 to 4 indices, enabling an O(n^2) solution.
REAL-WORLD CONNECTION
In distributed log aggregation, you often need to match request and response pairs that share the same identifier. By hashing the identifier you can quickly pair them regardless of their positions in the log stream, mirroring the pair‑sum grouping used here.
When implementing the hash map, store pairs sorted by their second index to allow a single pass that counts compatible later pairs in O(1) amortized time per pair, avoiding nested loops over all pairs.
COMPLEXITY AT A GLANCE
O(n^2)O(n^2)Core Theory — Why This Approach?
The key observation is that the two 7‑element sums in a 9‑length subsequence overlap on five elements. When the sums are equal, the overlapping terms cancel, leaving the simple equation a1 + a2 = a8 + a9. Thus the problem reduces to finding all ordered pairs of indices (i1, i2) and (i8, i9) with i1 < i2 < i8 < i9 such that the sums of the two elements are equal, and then choosing any five indices between i2 and i8 to serve as the middle part of the subsequence. A naive approach would enumerate all
C(n,9) subsequences, which is O(n^9) and infeasible for n > 20. The optimal paradigm uses a two‑sum style hash map: compute all pair sums in O(n^2) time, group pairs by sum, and for each sum iterate over pairs in order of their second index. For each first pair, we can efficiently count (or enumerate) all compatible second pairs that start after the first pair’s second index, and for each such pair compute the number of ways to pick five middle elements using combinatorial formulas. This reduces the search space from exponential to quadratic in n, while still allowing enumeration of all valid subsequences if required.
Interview Questions on This Problem
Q1How would you modify the algorithm if the subsequence length were 11 instead of 9?
For length 11 the overlapping region is 7 elements, so the condition becomes a1 + a2 + a3 = a9 + a10 + a11. We would precompute sums of all 3‑element prefixes and all 3‑element suffixes, store them in hash maps keyed by sum, and then for each prefix pair find matching suffixes that start after the prefix’s last index. The middle 5 elements are chosen from the indices between the two groups, again using combinatorics.
Q2In a distributed system, how could you parallelize the pair‑sum computation?
Split the array into chunks and assign each worker to compute pair sums for indices within its chunk and with indices in subsequent chunks. Each worker emits (sum, (i, j)) pairs to a central aggregator that merges them by sum. Because the pair‑sum computation is embarrassingly parallel, you can achieve near‑linear speedup with the number of workers, limited only by communication overhead when merging the hash maps.
Q3What is the worst‑case number of valid subsequences for an array of size n?
In the worst case (e.g., all elements equal), every pair of indices has the same sum, so for each sum we have C(n,2) pairs. For each pair (i1,i2) we can pair it with any later pair (i8,i9), giving roughly C(n,2)^2 / 4 ≈ O(n^4) valid pair combinations. For each such combination there are C(k,5) ways to choose the middle 5 indices, where k = i8 - i2 - 1. Thus the total number of subsequences can be as high as O(n^9) in the worst case, which explains why enumeration is only feasible for small n.
Examples
Input
sequence = [1, 2, 3, 4, 5, 4, 3, 2, 1]
Output
1
Explanation: The only subsequence of length 9 is the array itself: [1, 2, 3, 4, 5, 4, 3, 2, 1]. Sum of first 7: 1+2+3+4+5+4+3 = 22. Sum of last 7: 3+4+5+4+3+2+1 = 22. The sums are equal. The middle element is 5. The maximum element in the subsequence is 5. Since 5 is the maximum, this subsequence is valid. Count = 1.
Input
sequence = [1, 1, 1, 1, 2, 1, 1, 1, 1]
Output
1
Explanation: The subsequence is [1, 1, 1, 1, 2, 1, 1, 1, 1]. Sum of first 7: 1+1+1+1+2+1+1 = 8. Sum of last 7: 1+1+2+1+1+1+1 = 8. The sums are equal. The middle element is 2. The maximum element is 2. Since 2 is the maximum, this subsequence is valid. Count = 1.
Input
sequence = [1, 2, 3, 4, 5, 6, 7, 8, 9]
Output
0
Explanation: The subsequence is [1, 2, 3, 4, 5, 6, 7, 8, 9]. Sum of first 7: 1+2+3+4+5+6+7 = 28. Sum of last 7: 3+4+5+6+7+8+9 = 42. The sums are not equal (28 != 42). Thus, no valid subsequences. Count = 0.
Input
sequence = [5, 1, 2, 3, 4, 3, 2, 1, 5]
Output
0
Explanation: The subsequence is [5, 1, 2, 3, 4, 3, 2, 1, 5]. Sum of first 7: 5+1+2+3+4+3+2 = 20. Sum of last 7: 2+3+4+3+2+1+5 = 20. The sums are equal. The middle element is 4. The maximum element in the subsequence is 5 (at indices 1 and 9). Since the middle element (4) is not the maximum (5), this subsequence is invalid. Count = 0.
Constraints
- 1 <= sequence.length <= 10^5
- -10^9 <= sequence[i] <= 10^9
- The answer is guaranteed to fit in a 64-bit integer.
Optimal Approach & Strategy
Compute all pair sums in O(n^2), group pairs by sum, and for each sum iterate over pairs sorted by second index to find compatible later pairs. For each compatible pair count the number of ways to choose five middle indices using combinatorics, achieving O(n^2) time.
Brute Force Approach
Enumerate every combination of 9 indices (O(n^9)), compute the two 7‑element sums for each, and check if they are equal. This is infeasible for moderate n.
Verified Code Solutions
function solution(sequence) {
let n = sequence.length;
let result = [];
for (let i = 0; i <= n - 9; i++) {
let sumFirst = 0;
let sumLast = 0;
for (let j = 0; j < 7; j++) {
sumFirst += sequence[i + j];
sumLast += sequence[i + j + 2];
}
sumFirst -= sequence[i + 7];
sumLast -= sequence[i + 8];
if (sumFirst === sumLast) {
let max = Math.max(...sequence.slice(i, i + 9));
if (sequence[i + 7] === max) {
result.push(sequence.slice(i, i + 9));
}
}
}
return result;
}class Solution {
public:
vector<vector<int>> solution(vector<int>& sequence) {
int n = sequence.size();
vector<vector<int>> result;
for (int i = 0; i <= n - 9; i++) {
int sumFirst = 0;
int sumLast = 0;
for (int j = 0; j < 7; j++) {
sumFirst += sequence[i + j];
sumLast += sequence[i + j + 2];
}
sumFirst -= sequence[i + 7];
sumLast -= sequence[i + 8];
if (sumFirst == sumLast) {
int max = INT_MIN;
for (int k = i; k < i + 9; k++) {
max = max > sequence[k] ? max : sequence[k];
}
if (sequence[i + 7] == max) {
vector<vector<int>> temp(result.begin(), result.end());
temp.push_back(vector<int>(sequence.begin() + i, sequence.begin() + i + 9));
result = temp;
}
}
}
return result;
}
};class Solution {
public int[][] solution(int[] sequence) {
int n = sequence.length;
int[][] result = new int[0][9];
for (int i = 0; i <= n - 9; i++) {
int sumFirst = 0;
int sumLast = 0;
for (int j = 0; j < 7; j++) {
sumFirst += sequence[i + j];
sumLast += sequence[i + j + 2];
}
sumFirst -= sequence[i + 7];
sumLast -= sequence[i + 8];
if (sumFirst == sumLast) {
int max = Integer.MIN_VALUE;
for (int k = i; k < i + 9; k++) {
max = Math.max(max, sequence[k]);
}
if (sequence[i + 7] == max) {
int[][] temp = new int[result.length + 1][9];
System.arraycopy(result, 0, temp, 0, result.length);
temp[result.length] = Arrays.copyOfRange(sequence, i, i + 9);
result = temp;
}
}
}
return result;
}
}def solution(sequence):
n = len(sequence)
result = []
for i in range(n - 8):
sum_first = 0
sum_last = 0
for j in range(7):
sum_first += sequence[i + j]
sum_last += sequence[i + j + 2]
sum_first -= sequence[i + 7]
sum_last -= sequence[i + 8]
if sum_first == sum_last:
max_val = max(sequence[i:i + 9])
if sequence[i + 7] == max_val:
result.append(sequence[i:i + 9])
return resultfunction solution(sequence) {
let n = sequence.length;
let result = [];
for (let i = 0; i <= n - 9; i++) {
let sumFirst = 0;
let sumLast = 0;
for (let j = 0; j < 7; j++) {
sumFirst += sequence[i + j];
sumLast += sequence[i + j + 2];
}
sumFirst -= sequence[i + 7];
sumLast -= sequence[i + 8];
if (sumFirst === sumLast) {
let max = Math.max(...sequence.slice(i, i + 9));
if (sequence[i + 7] === max) {
result.push(sequence.slice(i, i + 9));
}
}
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.