Find the number of visible boxes after inserting smaller size boxes into bigger size boxes.

Given an array of integers, each number represents the size of its box. A smaller size box can fit into a larger size box, whereas the same or larger size boxes can’t fit into one another. Let us see this problem with the below example.

// Example
inp[] = {3, 3, 3, 4, 4, 2}
2 fits into 3, 3 fits into 4 and one 3 can not fit into another, finally only 3 boxes left.

If we observe the above example, whatever the sized box appears most of the time, that occurrence becomes the output of the problem (because we can’t fit similar size boxes into one another). Indirectly the problem here is to find the maximum number of occurrences that any one item has in an array. Here in the above example, it left with three boxes which can not further fit into one another.

Now, let us see the code for this approach.

int visibleBoxes(int arr[], int len)
{
    unordered_map<int, int> res;
    for (int i = 0; i < len; i++)
    {
        if (res.find(arr[i]) != res.end())
        {
            res[arr[i]]++;
        }
        else
        {
            res[arr[i]] = 1;
        }
    }
    unordered_map<int, int>::iterator itr;
    int result = 0;
    for (itr = res.begin(); itr != res.end(); itr++)
    {
        if (result < (*itr).second)
        {
            result = (*itr).second;
        }
    }
    return result;
}

The runtime for the above approach is O(n) with an extra O(n) space for map. Let us see complete executable code with main function.

// Output
Visible boxes are: 3

There are many number of ways to find the number of visible boxes after putting smaller size boxes into bigger sized ones. In the above article, we are using one of the best approaches with linear time and space complexity. If you know any better approach to solve this problem, please let our readers know by commenting here below. Happy Learning!.

Advertisements