Few days ago I got asked this fun problem in an interview. I quickly found the pattern I needed to solve it but failed miserably when trying to code it 🥲. As it could not be otherwise, just as the interview finished, my super programmer powers returned instantly, so I decided to start this section of my blog with such a cool problem.
The Problem
Given array xs of room temperatures (temperatures are always positive), we need to generate a new array where each ith position is:
- greater than
xs[i] - greater than greatest temperature found so far in the array
If both conditions are not met, use -1.
Example:
input: [3, 4, 5, 1, 2, 3, 9]
ouput: [4, 5, 9, 9, 9, 9, -1]
input: [13, 7, 6, 12]
output: [-1, 12, 12, -1]
input: [5, 4, 3, 2]
ouput: [-1, -1, -1, -1]
My Solution
My mistake was not dedicating more focus to the core case which is the procedure to return the proper value given the meet conditions.
Solution 1
| Complexity | |
|---|---|
| Time | |
| Space |
const findNextGreaterIndex = <T>(startAt: number, collection: T[]): number => {
for (let i = startAt; i < collection.length; i++) {
if (collection[i] > collection[startAt]) {
return i;
}
}
return -1;
}
const findNextGreaterTemperatures = (temps: number[]): number[] => {
const greaterTemps: number[] = [];
for (let i = 0; i < temps.length; i++) {
const k = findNextGreaterIndex(i, temps);
if (k === -1) {
greaterTemps.push(-1);
} else {
greaterTemps.push(Math.max(greaterTemps[i - 1] ?? 0, temps[k]));
}
}
return greaterTemps;
}
Solution 2
| Complexity | |
|---|---|
| Time | |
| Space |
This one took longer than I thought, since I realised I could start building the potential "next greater elements" from the end of the array, and keep them in a stack that:
- whenever I find a temperature that is less than the top of the stack, I use the top of the stack as the next greater temperature, and add the new element to the top of the stack as a potential next greater temperature.
- if the current temperature is greater than the top of the stack, then we need to unwind the stack (this won't affect the time complexity since at most we are going to unwind each element once) until the top of it is greater, so we can do the same as in step 1.
class Stack<T> {
private items: T[];
constructor() {
this.items = [];
}
push(item: T): void {
this.items.push(item);
}
peek(): T {
if (this.isEmpty()) {
throw new Error('stack is empty')
}
return this.items[this.items.length - 1];
}
pop(): T {
if (this.isEmpty()) {
throw new Error('stack is empty');
}
return this.items.pop() as T;
}
isEmpty(): boolean {
return this.items.length === 0;
}
}
const findNextGreaterTemperatures = (temps: number[]): number[] => {
const N = temps.length;
const potentialNextGreaters = new Stack<number>();
const greaterTemps: number[] = [];
for (let i = N - 1; i >= 0; i--) {
const current = temps[i];
while (!potentialNextGreaters.isEmpty() && current > potentialNextGreaters.peek()) {
potentialNextGreaters.pop();
}
if (potentialNextGreaters.isEmpty()) {
greaterTemps[i] = -1;
potentialNextGreaters.push(current);
continue;
}
greaterTemps[i] = potentialNextGreaters.peek();
potentialNextGreaters.push(current);
}
return greaterTemps;
};
Finally, up until this point, we are finding the next greater temperature for each ith element but not taking into account the maximum temperature found so far. We fix it by performing an extra loop at the end (this won't affect the time complexity) that will adjust the array to be monotonically increasing.
class Stack<T> {
private items: T[];
constructor() {
this.items = [];
}
push(item: T): void {
this.items.push(item);
}
peek(): T {
if (this.isEmpty()) {
throw new Error('stack is empty')
}
return this.items[this.items.length - 1];
}
pop(): T {
if (this.isEmpty()) {
throw new Error('stack is empty');
}
return this.items.pop() as T;
}
isEmpty(): boolean {
return this.items.length === 0;
}
}
const findNextGreaterTemperatures = (temps: number[]): number[] => {
const N = temps.length;
const potentialNextGreaters = new Stack<number>();
const greaterTemps: number[] = [];
for (let i = N - 1; i >= 0; i--) {
const current = temps[i];
while (!potentialNextGreaters.isEmpty() && current > potentialNextGreaters.peek()) {
potentialNextGreaters.pop();
}
if (potentialNextGreaters.isEmpty()) {
greaterTemps[i] = -1;
potentialNextGreaters.push(current);
continue;
}
greaterTemps[i] = potentialNextGreaters.peek();
potentialNextGreaters.push(current);
}
// Adjust the array of temperatures to be monotonically increasing.
for (let i = 0; i < N - 1; i++) {
if (greaterTemps[i+1] !== -1 && greaterTemps[i] > greaterTemps[i + 1]) {
greaterTemps[i+1] = greaterTemps[i];
}
}
return greaterTemps;
};