Ninja and Locker

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
4 upvotes
Asked in company
Flipkart limited

Problem statement

Ninja has two arrays ‘CASH’’ and ‘LOCKER’ denoting the height of each stack of cash of unit width and height of ‘N’ sections in the locker respectively.

The locker sections are labeled from 0 to ‘N’ - 1 from left to right.

Cash stacks can only be put in the locker by following the certain rules:

  • Cash stacks can’t be piled up

  • You can take any order of cash stack

  • You can push the stack in the locker only from left to right

  • If height of some stack is greater than the height of locker section then the stack will be stopped before that room

    • Ninja wants your help to find the maximum number of cash stacks he can put into the locker.

    For Example: 
    As we can see from the example below we are only able to put two stacks in the locker so our answer will be 2.

    Detailed explanation ( Input/output format, Notes, Images )
    Input Format: 
    The first line of input contains an integer 'T' representing the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the size of ‘CASH’ and ‘LOCKER’ arrays respectively.

The second line of each test case contains ‘N’ space-separated integers denoting the elements of ‘CASH’. 

The third line of each test case contains ‘M’ space-separated integers denoting the elements of ‘LOCKER’.
    Output Format: 
    For each test case, print the maximum number of cash stacks that ninja can put in the locker.

The output of each test case will be printed in a separate line.
    Constraints: 
    1 <= T <= 5
1 <= N,M <= 5000
1 <= CASH[i], LOCKER[i] <= 10^9

Where ‘T’ is the number of test cases, ‘N’ and ‘M’ is the size of ‘CASH’ and ‘LOCKER’ respectively, and 'CASH[i]' and 'LOCKER[i]' denotes the 'i-th' elements of the array.

Time limit: 1 sec
    Note: 
    You do not need to print anything, it has already been taken care of. Just implement the given function.
    Sample Input 1:
    2
3 3
1 2 3
2 2 1
4 3
4 3 2 5
4 2 3
    Sample Output 1:
    2
2
    Explanation of Sample Input 1:
    Test Case 1 :  
We can put at most two cash stacks in the locker.


    Test Case 2 : 
We can see in the below image we can put at most 2 cash stacks.

    Sample Input 2:
    2
4 5
5 9 4 2
5 4 3 2 1
4 4
1 1 1 1
1 2 3 4
    Sample Output 2:
    3
4
    Hint

    Try to place the minimum possible cash stack in the locker first.

    Approaches (2)
    Brute Force

    The idea here is to put the smallest possible cash stack in the locker first and if no stack is available then we check the next section.

    To implement this we first need to make a valid locker ‘VALIDLOCKER’ in which if VALIDLOCKER[i] < VALIDLOCKER[i+1], then the maximum height of section VALIDLOCKER[i+1] is VALIDLOCKER[i].

    After this we will iterate ‘LOCKER’ section one by one and find the minimum possible cash stack to put in this section.

    Algorithm:

    • Declare array ‘VALIDLOCKER’ and ‘PLACED’ initialise to 0.
    • Declare a variable ‘ANS’ := 0
    • for( i: 0 - > LOCKER.size )
      • VALIDLOCKER[i] = minimum of VALIDLOCKER[i-1] and LOCKER[i]
    • for ( i : VALIDLOCKER.size -1 -> 0 )
      • Declare a variable ‘MAXCASH’ = VALIDLOCKER[i]
      • Find the minimum cash and assign its value to ‘MAXCASH’ and make ‘PLACED[i]’ = 1.
      • If we are unable to find a cash stack then continue else increment ‘ANS’.
    • return ‘ANS’
    Time Complexity

    O(N * M ), where ‘N’ and ‘M’ is the size of ‘CASH’ and 'LOCKER’ respectively.

     

    We are iterating ‘CASH’ array for each index of ‘LOCKER’ which takes 0( N * M ). Hence, the overall time complexity is O(N * M).

    Space Complexity

    O(M), where ‘M’ is the size of the ‘LOCKER’ array.

     

    To make a ‘VALIDLOCKER’ array we need to make an array of size O(M). Hence, the overall space complexity is O(M).

    Code Solution
    (100% EXP penalty)
    Ninja and Locker
    Full screen
    Console