Algorithm to divide a chain (array) into three pieces-CodePudding

I've been doing some interviews and technical exercises and a few days ago I came across an exercise where I had to return "the minimal cost of dividing a chain into three pieces". I wasn't able to do it at the moment, I ran out of time, but I kept working on it until I reached a solution.

Problem

An array A consisting of N integers is given. The elements of array A together represent a chain, and each element represents the strength of each link in the chain. We want to divide this chain into three smaller chains. All we can do is break the chain in exactly two non-adjacent positions. More precisely, we should break links P,Q (0 < P < Q < N - 1, Q - P > 1), resulting in three chains [0, P - 1], [P 1, Q - 1], [Q 1, N - 1]. The total cost of this operation is equal to A[P] A[Q].

For example, consider an array such that:

A[0] = 5
A[1] = 2
A[2] = 4
A[3] = 6
A[4] = 3
A[5] = 7

We can choose to break the following links:

 (1-3): total cost is 2   6 = 8
 (1-4): total cost is 2   3 = 5
 (2-4): total cost is 4   3 = 7

Write a function class Solution { public int solution(int[] A); } that, given an array A of N integers, returns the minimal cost of dividing the chain into three pieces. Given the example above, the function should return 5.

My solution

public static int solution(int[] A) {
        int cap = A.length;
        int minCostCut = 0;
        int from = 0;
        int to = 0;
        for (int i = 1; i < cap - 1; i  ) {
            for (int j = 1; j < cap - 1; j  ) {
                if (j - i >= 2) {
                    int cost = A[i]   A[j];
                    if (minCostCut == 0 || minCostCut > cost) {
                        minCostCut = cost;
                        from = i;
                        to = j;
                    }
                }
            }
        }

        //System.out.println("Minimum Cost of dividing is from: "   from   " to: "   to   " is: "   minCostCut);

        return minCostCut;
}

I'm not confident about that code so I would like to know if you see something I can optimize here.

CodePudding user response：

Should be on codereview but hey! You're here. This will probably get closed but it's good practice to work these things through occasionally :)

So, once we have a correct solution (which you do), this becomes a complexity challenge.

Your method is O(N^2) since j loops the whole array for each element i in the array hence scales N*N for any given length of content.
It can be tweaked to become O(N log N) by j scanning the remainder of the array for each element i. No point re-scanning anything behind i as we already have the cheapest pair found so far.
It can also written O(N) by comparing each element to the cheapest element at least two links behind. This prev_best item is simple to remember as you move along the array (once).
I do not believe we can improve on O(N) given this problem insists on costing every pair.

import java.util.stream.IntStream;

public class SO69929295 {
  
  public static int[] solve_O_N(int... chain) {
    int from = 1, to = 3, prev_best = 1; // cheapest link _at least two links behind to_
    int cheapest = Integer.MAX_VALUE;

    for (int i = 3; i < chain.length - 1; i  ) {
      if (chain[i - 2] < chain[prev_best]) prev_best = i - 2;

      int cost = chain[i]   chain[prev_best];
      if (cost < cheapest) {
        from = prev_best;
        to = i;
        cheapest = cost;
      }
    }

    return new int[] {from, to};
  }
  
  public static int[] solve_O_NlogN(int... chain) {
    int minCostCut = Integer.MAX_VALUE;
    int from = 0;
    int to = 0;
    for (int i = 1; i < chain.length - 1; i  ) {
      for (int j = i   2; j < chain.length - 1; j  ) { // Scan *remainder* of chain
        int cost = chain[i]   chain[j];
        if (cost < minCostCut) {
          minCostCut = cost;
          from = i;
          to = j;
        }
      }
    }
    return new int[] {from, to};
  }

  public static void solveAndLog(int... chain) {
    IntStream.of(chain).forEach(i -> System.out.printf("d ", i));
    System.out.println();

    int[] fromto = solve_O_NlogN(chain);
    IntStream.range(0, chain.length).forEach(i -> System.out.print(i == fromto[0] || i == fromto[1] ? "^^ " : "   "));
    System.out.println();

    int[] fromto2 = solve_O_N(chain);
    IntStream.range(0, chain.length).forEach(i -> System.out.print(i == fromto2[0] || i == fromto2[1] ? "^^ " : "   "));
    System.out.println();
  }
  
  public static void main(String[] args) {
    // Array of chain links graded by strength. Find cheapest two links to cut producing three chains (of length > 1).
    solveAndLog(1, 5, 2, 4, 6, 3, 7);
    solveAndLog(1, 5, 2, 3, 6, 4, 7);
    solveAndLog(1, 1, 1, 1, 1, 1, 1);
    solveAndLog(1, 2, 3, 4, 5, 6, 7);
    solveAndLog(7, 6, 5, 4, 3, 2, 1);
    solveAndLog(IntStream.generate(() -> (int)(Math.random() * 100)).limit(30).toArray());
  }
}

prints something like this

28 34 89 10 21 17 99 91 23 54 91 81 89 61 15 02 27 47 84 47 36 81 61 68 84 52 25 64 65 43 
         ^^                                  ^^

If you want to get a feel for how much complexity impacts then try this:

    int[] chain = IntStream.generate(() -> (int)(Math.random() * 100)).limit(1_000_000).toArray();
    System.out.println(Arrays.toString(solve_O_N(chain)));
    System.out.println(Arrays.toString(solve_O_NlogN(chain)));

The first solves instantly, the second ... well I gave up waiting!