Find the minimum number of pieces so that the original sequence can be rearranged to form the desired sequence (time limit)

Question

Can someone tell me how to find an effective solution to the problem below?

I can solve the problem for some small input, but I exceeded the time limit when solving more complex cases (ex array with 450,000 elements and a time limit of ~ 5.5 sec).

You are given two arrays with numbers from 1 to N, written in random order.

Example:

// numbers from 1 to 4
int[] o = new int[] { 1, 4, 3, 2 }; // original
int[] d = new int[] { 1, 2, 4, 3 }; // desired

Find the minimum number of fragments of the original sequence so that these parts can be rearranged to form the desired sequence.

In the above example, an example of a minimum number of pieces is 3, as an initial sequence:

{1, 4, 3, 2}      // original

can be divided into:

{1}, {4, 3}, {2}

and these parts can be rearranged to form the desired sequence:

{1}, {4, 3}, {2}
{1}, {2}, {4, 3}
{1, 2, 4, 3}      // desired

Answer 1

Here is the version that works in O (n). The idea is to replace the numbers so that the target array becomes [0, 1, 2, 3, ...], so it’s very easy to count the number of cuts required. Here is the implementation in Javascript ( link ):

function solve(o, d) {
  var sub = [], count = 0;
  // make arrays 0-based and calculate substitution
  for (var i = 0; i < d.length; i++) {
    o[i]--;
    d[i]--;
    sub[d[i]] = i;
  }
  // substitute
  for (var i = 0; i < o.length; i++)
    o[i] = sub[o[i]];
  // scan and count
  for (var i = 1; i < o.length; i++)
    if (o[i - 1] + 1 != o[i])
      count++;
  return count + 1; // the number of pieces is the number of required cuts + 1
}

alert(solve([1, 4, 3, 2], [1, 2, 4, 3]));