Find maximum value of array chunks minima (Javascript)

Question

I just did a HackerRank challenge, but my code kept failing 3 tests, with a timeout error. These tests were probably passing very large arrays as arguments (constraints said the arrays could have as many as 10⁹ elements).

I researched some performance bottlenecks in my code (Array.slice, Math.min and Math.max, getting rid of unnecessary loops, etc) and optimized them all, but these tests were still failing. Is there a better way to approach this problem?

The statement:

Given an integer array space of length n, divide it into segments of size x, find the minimum value of each segment, then return the maximum value of all encountered minima.

Example:

x = 2
space = [8, 2, 4, 6]
segments:
[8, 2]
[2, 4]
[4, 6]
minima: [2, 2, 4]
// Final answer: 4

Can't remember the constraints exactly but it was something like:
1 ≤ x ≤ n
1 ≤ n ≤ 10⁹
1 ≤ space[i] ≤ 10⁹

My code:

function segment(x: number, space: number[]): number {
 let left = 0;
 let right = x;
 let max = 0;
 for (let i = 0; i < space.length; i++) {
 if (space[right - 1] === undefined) {
 break;
 }
 let localMin = Infinity;
 for (let j = left; j < right; j++) {
 if (space[j] < localMin) {
 localMin = space[j];
 }
 }
 if (localMin > max) {
 max = localMin;
 }
 left++;
 right++;
 }
 return max;
}
console.log(segment(2, [8, 2, 4, 6])); // 4

• greybeard: I have an inkling the problem is either misinterpreting the problem (statement) - please hyperlink the original - or not reusing (intermediate) results.
• rschpdr: I'm afraid I can't post the link to the original problem because it's one of those company interview problems that are only accessible to candidates that receive the link by email. But I found a Stack Overflow question about the same problem, maybe it's better explained there: stackoverflow.com/questions/66079780/…

Answer 1

I find it easy to spot the one problem with the code presented that can't be fixed without outside information:

It contains no "testable" specification, gives no clue as to what it is to accomplish. Use some accepted means of documentation - I've heard of JSDoc.

The approach I see taken in the code is brute force: compute a summary information about multitudes independently from their elements - ignoring large overlap.
These problems are crafted to have brute force fail no matter the amount of force.

So after identifying the minimum of the first x items, what will be the minimum with "item 0 excluded and item x included"? Conceivably, that depends:
1) item 0 was the only item with minimum value
i) some other item is minimal
a) item 0 was minimum as well as others
I) item x is the new minimum
- never mind, the important takeaway is that the minimum changes "at the edges of the window", if at all.

So, what is the most simple thing that might suffice?
Take a look at i)&I): if the value wasn't the minimum, and the value entering it was larger, the minimum remains unchanged. (Try to asses the worst case performance of this.)
Then, there may be a suitable data structure for what's needed - spec it:
- report minimum
- remove by value/index in the input/"time" in the data structure
- add to the data structure
A balanced search tree(allowing for repeated keys) should fit the bill, there are bound to be better.

The code manipulates i without ever using it.
The loop is belt and braces, checking a limit and a termination condition: better use either
while (space[right - 1] !== undefined) or
for (let left = 0 ; (right = left + x) <= space.length ; left++)