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

Question

Can anybody give me a hint how to find efficient solution for the problem below?

I can solve the problem for some small input but I exceed time limit when solving more difficult cases (e.x. array with 450000 elements and time limit ~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 pieces of the original sequence so that those pieces can be rearranged to form the desired sequence.

In the example case above the minimal number of pieces is 3, as the original sequence:

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

can be split into:

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

and those pieces can be rearranged to form the desired sequence:

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

Answer 1

Because I still received comments after 5 years I decided to add another (better) solution below, but first the original one:

Here is a version that runs in O(n). The idea is to substitute the numbers so that the destination array becomes [0, 1, 2, 3, ...] then it is very simple to count the number of required cuts. Here is an 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]));

---

As requested, more explanation:

1. With the substitution the target becomes 0, 1, 2, ...
2. Now if we look at a number at index i, then the number at index i - 1 has to be exactly one smaller or we have to cut there, that's the whole point of the substitution.

---

This is not the only O(n) solution. Instead of the substitution you could create a lookup table that tells you what number comes before it. Like that you don't have to modify the input. It is the more elegant solution in my opinion (this algorithm works for any array with unique elements, e.g. in Java with String arrays you would create a HashMap<String, String> for the lookup):

    function solve(o, d) {
        let lookup = []
        for (let i = 0; i < d.length - 1; i++)
            lookup[d[i + 1]] = d[i]
        let pieces = 1
        for (let i = 0; i < o.length - 1; i++)
            if (lookup[o[i + 1]] != o[i])
                pieces++
        return pieces
    }
    console.log(solve([1, 4, 3, 2], [1, 2, 4, 3]))