Java Coding Question - Find Next Earning Opportunity

Solving Interesting Coding Question In Java

Question

You have been given an array of days with the income you can make. You need to find, for each day, the immediate next day where income is higher than the current day’s income.

income_oportunity = [1,2,0,1,3,4,5,0,3,5,6,2,1,4,10,0]

So, for day 0 -> the immediate next good day where one can make more money is day 1

For day 1 -> the immediate next good day where one can make money is day 4

Answer

Naive Approach:

• For each day → We scan forward the rest of the days and find the first greater income and add that to the result.

• But the time complexity for that solution would become O (n^2) because we need to traverse the rest of the array forward for each day.

Time complexity: O(n^2)
Space complexity: O (1) ( not including memory needed for result array itself )

Optimized Approach:

• One optimization we can do is to trade off memory over time. While we traverse our income array, for days when we are not sure which day will have the greater income, we can add them to a stack to solve that later.

• In the future, when we find a day for which the income is higher than the previous days that we stored in a stack, we can easily solve those unsolved days back in the stack.

• Algorithm :

  • We keep a stack of indices where we haven’t yet found a better future day.

  • For each day i, if its income is higher than the income at the index on top of the stack, then i is the "next good day" for that earlier day.

  • We pop and update until the condition breaks.

  • Push i into the stack to wait for its own next good day.

  • Days left in the stack at the end have no better day (stay -1).

Time complexity: O(n)
Space complexity: O(n)

Complete Solution:

This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters

Show hidden characters

	package Easy;
	import java.util.Arrays;
	import java.util.Stack;
	/**
	*
	*
	* We have been given array of days with income one can make.
	* [1,2,0,1,3,4,5,0,3,5,6,2,1,4,10,0]
	* so for day 0 -> next good day where one can make more money is day 1
	* for day 1 -> next good day where one can make money day 4
	*/
	public class NextOpportunity {
	public static void main(String[] args) {
	int[] incomes = {1, 2, 0, 1, 3, 4, 5, 0, 3, 5, 6, 2, 1, 4, 10, 0};
	int[] nextDay = findNextOpportunity(incomes);
	for (int i = 0; i < incomes.length; i++) {
	System.out.println("Day " + i + " (income=" + incomes[i] + ") -> " +
	(nextDay[i] == -1 ? "No better day" : "Day " +
	nextDay[i] + " (income=" + incomes[nextDay[i]] + ")"));
	}
	}
	private static int[] findNextOpportunityNaive(int[] arr) {
	int n = arr.length;
	int[] result = new int[n];
	Arrays.fill(result, -1); // default: no better day
	for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
	if (arr[j] > arr[i]) {
	result[i] = j;
	break; // stop at the first greater element
	}
	}
	}
	return result;
	}
	private static int[] findNextOpportunity(int[] incomes) {
	int n = incomes.length;
	int[] result = new int[n];
	Arrays.fill(result, -1); // default: no better day
	Stack<Integer> stack = new Stack<>();
	for (int i = 0; i < n; i++) {
	while (!stack.isEmpty() && incomes[i] > incomes[stack.peek()]) {
	int prevIndex = stack.pop();
	result[prevIndex] = i; // found the next higher income day
	}
	stack.push(i);
	}
	return result;
	}
	}

view raw NextOpportunity.java hosted with ❤ by GitHub

More Java/Spring Interview Coding Questions

More Java/Spring Interview Quizzes

Top Java/Spring Blogs