Find minimum sum from given array

Question

I have an array of numbers [3,4,5,1,2,3,1] find 3 pairs sub sequence say sub[] such that sub[0] < sub[1] > sub[2], sum those 3 elements and get the minimum sum.

Example:

For [3,4,5,1,2,3,1], I can select [1,2,1] here 1<2>1 so sum is 1+2+1 = 4 which is minimum.

Constraints:

array size upto 1,00,000 each element size is 1 to 1,00,00,00,000

My approach is using 3 nested for loops and getting the minimum sum which is not an efficient way.

public long process(List<Integer> list) {
   int n = list.size();
   long output = Long.MAX_VALUE;
   for(int i=0; i<n; i++) {
      for(int j=i+1; j<n; j++) {
       if(list.get(i) < list.get(j)) {
          for(int k=j+1; k<n; k++) {
            if(list.get(j) > list.get(k)) {
               output = Math.min(output, list.get(i)+list.get(j)+list.get(k));
             }
          }
       }
      }
   }
   return output;
}

How do solve this program efficiently with less time complexity?

Answer 1

Let me provide a solution whose time complexity is O(n) and space complexity is O(n). You have to iterate through the array thrice and also store two arrays for the minimum elements. I was inspired by the comment made by @Someone. Please keep in mind that this solution makes the assumption that for any sub[i] < sub[j] > sub[k] this must hold: i < j < k.

Solution can be modified easily to cover the cases where i <= j <= k. If it's not compulsory for this equation to hold, then question becomes more trivial. Just find first three minimum element and we know that sub[i] < sub[j] > sub[k] holds. Make sure that the third one (largest one) is different than the others. Although you didn't specify the rule I mentioned above, I believe question wants you to comply with that rule - otherwise that would be very trivial.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Stackoverflow {
    public static void main(String[] args) {
        ArrayList<Integer> numbers = new ArrayList<>(Arrays.asList(3,4,5,1,2,3,1));
        System.out.println(process(numbers));
    }
    
    public static long process(List<Integer> list) {
        if(list.size() < 3) return -1; // not enough elements
        
        int n = list.size();
        
        int[] minLeft = new int[n];
        int[] minRight = new int[n];
        
        minLeft[0] = list.get(0);
        minRight[minRight.length - 1] = list.get(list.size() - 1);
        
        // store the minimum elements from left up to current index
        for(int i=1; i<n; i++) {
            minLeft[i] = Math.min(list.get(i), minLeft[i - 1]);
        }
        
        
        // store the maximum elements from right up to current index
        for(int i=n - 2; i>=0; i--) {
            minRight[i] = Math.min(list.get(i), minRight[i+1]);
        }
        
        
        long sum = Integer.MAX_VALUE;
        
        for(int i=1; i<n-1; i++) {
            sum = Math.min(sum, minLeft[i - 1] + list.get(i) + minRight[i + 1]);
        }
        
        return sum;
    }
}

Output:

4