Given an array of best fit sizes , tell how many elements from the other array can be fitted(more details below)

Question

There is an old dry well. Its sides are made of concrete rings. Each such ring is one meter high, but the rings can have different (internal) diameters. Nevertheless, all the rings are centered on one another. The well is N meters deep; that is, there are N concrete rings inside it. You are about to drop M concrete disks into the well. Each disk is one meter thick, and different disks can have different diameters. Once each disk is dropped, it falls down until:

• it hits the bottom of the well;
• it hits a ring whose internal diameter is smaller then the disk's diameter; or
• it hits a previously dropped disk. (Note that if the internal diameter of a ring and the diameter of a disk are equal, then the disk can fall through the ring.)

The disks you are about to drop are ready and you know their diameters, as well as the diameters of all the rings in the well. The question arises: how many of the disks will fit into the well?

Write a function: int falling_disks(int A[], int N, int B[], int M); that, given two zero-indexed arrays of integers − A, containing the internal diameters of the N rings (in top-down order), and B, containing the diameters of the M disks (in the order they are to be dropped) − returns the number of disks that will fit into the well. For example, given the following two arrays:

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

the function should return 4, as all but the last of the disks will fit into the well. The figure shows the situation after dropping four disks.

Assume that:

• N is an integer within the range [1..200,000];
  • M is an integer within the range [1..200,000];
  • each element of array A is an integer within the range [1..1,000,000,000];
  • each element of array B is an integer within the range [1..1,000,000,000].

Complexity:

• expected worst-case time complexity is O(N);
  • expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
  • Elements of input arrays can be modified.

I tried using a stack and doing something , but i am not able to get to O(n) solution , the worst case still remains O(n^2) even after some optimizations i think.

Answer 1

First you need to modify the given internal diameters of the rings to fill up the unnecessary gaps. Suppose you have a ring of internal diameter 5 below a ring with internal diameter 2. Any disk of size greater than 2 will not be able to reach that ring. So we can change the internal diameter of the lower ring to 2. Basically we are filling up the gaps.

before:

after:

Use the following algorithm:

1. min = A[0]
2. i = 1
3. if i == N then STOP
4. if A[i] < min then min = A[i]
5. if A[i] > min then A[i] = min
6. i++
7. go to step 3

Now that the rings have formed a structure where each lower ring has an internal diameter lesser than or equal to the internal diameter of the upper ring, the next part is fairly simple. We will start inserting the disks from the bottom. If the first disk fits the lowest ring then fine otherwise we move on to the ring above it and so on. You can use an algorithm like:

1. i = N-1
2. j = 0
3. if i < 0 or j == M then STOP
4. if A[i] >= B[j] then j++
5. i--
6. go to step 3

The final value of the variable j is the required answer.

Answer 2

public static int falling_disks(int[] A, int[] B)
{
    int mymin = A[0];
    int nbDisk = 0;

    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] < mymin) mymin = A[i];
        if (A[i] > mymin) A[i] = mymin;               
    }             

    for (int i = A.Length - 1; i >= 0; i--) 
    {
        if (B[nbDisk] <= A[i]) nbDisk++;
        if (nbDisk == B.Length) break;
    }           

    return nbDisk;
 }