Problem

Given an array of integers, find three indexes i, j, k such that i < j < k and arr[i] < arr[j] < arr[k].

Examples

Example 1:

Input: arr = [1, 2, 1, 3, 0, 4, 6, 2]
Output: [0, 1, 5]

Explanation:
- The elements at these indices are arr[0] = 1, arr[1] = 2, and arr[5] = 4, which satisfies the condition 1 < 2 < 4.

Solution

Method 1 - Using left min and right max arrays

Here is the approach:

  1. Precompute Left Min and Right Max Arrays:
    • Create an array left_min where left_min[i] holds the index of the smallest element to the left of i.
    • Create an array right_max where right_max[i] holds the index of the largest element to the right of i.
  2. Find the middle element:
    • Iterate through each element and check if it has a valid left and right element such that arr[left_min[i]] < arr[i] < arr[right_max[i]].

Code

Java
public class Solution {

    public int[] findThreeIndices(int[] arr) {
        int n = arr.length;

        if (n < 3) {
            return new int[0];
        }

        int[] left_min = new int[n];
        int min_index = 0;
        left_min[0] = -1;

        for (int i = 1; i < n; i++) {
            if (arr[i] <= arr[min_index]) {
                left_min[i] = -1;
                min_index = i;
            } else {
                left_min[i] = min_index;
            }
        }

        int[] right_max = new int[n];
        int max_index = n - 1;
        right_max[n - 1] = -1;

        for (int i = n - 2; i >= 0; i--) {
            if (arr[i] >= arr[max_index]) {
                right_max[i] = -1;
                max_index = i;
            } else {
                right_max[i] = max_index;
            }
        }

        for (int j = 1; j < n - 1; j++) {
            if (left_min[j] != -1 && right_max[j] != -1) {
                return new int[]{left_min[j], j, right_max[j]};
            }
        }

        return new int[0];
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 3, 0, 4, 6, 2};
        int[] result = new Solution().findThreeIndices(arr);
        System.out.println(Arrays.toString(result)); // Expected output could be: [0, 1, 5]
    }
}
Python
from typing import List

class Solution:
    def find_three_indices(self, arr: List[int]) -> List[int]:
        n = len(arr)
        
        if n < 3:
            return []

        left_min = [-1] * n
        min_index = 0

        for i in range(1, n):
            if arr[i] <= arr[min_index]:
                left_min[i] = -1
                min_index = i
            else:
                left_min[i] = min_index

        right_max = [-1] * n
        max_index = n - 1

        for i in range(n - 2, -1, -1):
            if arr[i] >= arr[max_index]:
                right_max[i] = -1
                max_index = i
            else:
                right_max[i] = max_index

        for j in range(1, n - 1):
            if left_min[j] != -1 and right_max[j] != -1:
                return [left_min[j], j, right_max[j]]

        return []

# Example usage
sol = Solution()
arr = [1, 2, 1, 3, 0, 4, 6, 2]
result = sol.find_three_indices(arr)
print(result)  # Expected output could be: [0, 1, 5]

Complexity

  • ⏰ Time complexity: O(n), where n is the number of elements in the array. Each element is processed a constant number of times.
  • 🧺 Space complexity: O(n) to store the left_min and right_max arrays.

Method 2 - Using only firstMin and second Min elements

Solving a smaller problem often helps in tackling a larger one. If we need to find just two such variables, it is straightforward: keep track of the minimum element so far, and print the pair when a higher element is found. The goal is to find any one such pair, not all pairs.

Similarly, to find any one triplet, we track two minimums — arr[i] and arr[j] until arr[k] is found. After identifying two minimums, if a new overall minimum is encountered, how should it be handled? This new minimum is crucial because the remaining numbers may be smaller than the current minimums but larger than this new overall minimum.

For eg. for array [20, 30, 5, 6, 1, 7], when we are at index 3:

[20, 30, 5, 6, 1, 7]
         ^
currSeries = [20, 30]
min = 5

This is managed by storing the new minimum as the start of a potential new series. If another number, less than the current series but larger than the potential minimum, is found, the current series can be discarded in favor of the potential minimum and current number.

[20, 30, 5, 6, 1, 7]
		    ^
current-series = 20, 30
potential min = 5
current num = 6
=> discard current-series and replace it with potential min and current num
=> current-series = 5, 6

Here is the approach:

  1. Initialize Variables:
    • Use first_min and second_min to keep track of indices of the smallest and the second smallest elements respectively.
    • Use potential_min to track a potential new minimum which might start a new triplet sequence.
  2. Iterate Through the Array:
    • If the current element is larger than second_min, return the triplet.
    • If the current element is larger than first_min but less than second_min, update second_min.
    • If a new minimum is found, update potential_min and handle the series accordingly.

Code

Java
public class Solution {

    public static int[] findThreeIndices(int[] arr) {
        int n = arr.length;
        if (n < 3) {
            return new int[0];
        }

        // Variables to store indices of the sequence
        int firstMin = -1;
        int secondMin = -1;
        int potentialMin = -1;

        for (int i = 0; i < n; i++) {
            if (firstMin == -1 || arr[i] <= arr[firstMin]) {
                firstMin = i; // Update first minimum
            } else if (secondMin == -1 || arr[i] <= arr[secondMin]) {
                secondMin = i; // Update second minimum
            } else {
                return new int[]{firstMin, secondMin, i}; // Found the third element of the triplet
            }

            if (potentialMin == -1 || arr[i] < arr[potentialMin]) {
                potentialMin = i; // Update potential new minimum
            } else if (arr[i] > arr[potentialMin]) {
                firstMin = potentialMin;
                secondMin = i;
                potentialMin = -1;
            }
        }

        return new int[0]; // If no triplet found
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 3, 0, 4, 6, 2};
        int[] result = findThreeIndices(arr);
        System.out.println(Arrays.toString(result)); // Expected output: [0, 3, 5]
    }
}
Python
class Solution:
    def find_three_indices(self, arr: List[int]) -> List[int]:
        n = len(arr)
        if n < 3:
            return []

        # Variables to store indices of the sequence
        first_min = -1
        second_min = -1
        potential_min = -1

        for i in range(n):
            if first_min == -1 or arr[i] <= arr[first_min]:
                first_min = i  # Update first minimum
            elif second_min == -1 or arr[i] <= arr[second_min]:
                second_min = i  # Update second minimum
            else:
                return [first_min, second_min, i]  # Found the third element of the triplet

            if potential_min == -1 or arr[i] < arr[potential_min]:
                potential_min = i  # Update potential new minimum
            elif arr[i] > arr[potential_min]:
                first_min = potential_min
                second_min = i
                potential_min = -1

        return []  # If no triplet found

# Example usage
sol = Solution()
arr = [1, 2, 1, 3, 0, 4, 6, 2]
result = sol.find_three_indices(arr)
print(result)  # Expected output: [0, 3, 5]

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)