Count minimum cost in array

Question

Count the number of minimum cost in the given array.

Codemia · Accepted Answer

To solve the problem of counting the number of occurrences of the minimum cost in the given array, we can utilize a **hash map** (dictionary in Python) to maintain a frequency count of each unique element in the array. This is suitable because it allows us to efficiently track how many times each element appears while iterating through the array only once. The **pattern** here is a frequency counting approach, which is optimal for problems that require counting occurrences of elements.

1. **Initialize a frequency dictionary**: Start with an empty dictionary to keep track of the counts of each element in the array.
2. **Find minimum cost**: As we populate the dictionary, also keep track of the minimum value encountered.
3. **Count occurrences**: After identifying the minimum value, simply retrieve its count from the dictionary.

**Example**: For the input array `arr = [3, 1, 2, 1, 4]`:
- Initialize an empty dictionary: `frequency = {}`.
- Iterate through `arr`:
  - For `3`: frequency becomes `{3: 1}`.
  - For `1`: frequency becomes `{3: 1, 1: 1}`.
  - For `2`: frequency becomes `{3: 1, 1: 1, 2: 1}`.
  - For the next `1`: frequency becomes `{3: 1, 1: 2, 2: 1}`.
  - For `4`: frequency becomes `{3: 1, 1: 2, 2: 1, 4: 1}`.
- The minimum value is `1`, and its count is `2`.

Here’s the Python code that implements the above approach:
```python
def count_minimum_cost(arr):
    if not arr:
        return 0  # Edge case for empty array

frequency = {}
    min_cost = float('inf')

# Count frequencies and find minimum cost
    for num in arr:
        if num in frequency:
            frequency[num] += 1
        else:
            frequency[num] = 1
        if num < min_cost:
            min_cost = num

return frequency[min_cost]  # Return the count of the minimum cost
```
This function checks for the edge case of an empty array and then counts frequencies while tracking the minimum value.

The **time complexity** of this solution is O(n), where n is the number of elements in the array. This is because we traverse the array once to fill the frequency dictionary and find the minimum value. The **space complexity** is O(k), where k is the number of unique elements in the array. In the worst case, where all elements are unique, the space complexity will be O(n). This is efficient given the constraints of the problem.

1. **Empty array**: If the input array is empty, return `0` since there are no elements to count.
2. **Single element array**: For an array with one element, such as `arr = [5]`, the function should return `1` since the only number is also the minimum.
3. **All elements are the same**: For an array like `arr = [2, 2, 2]`, the function should return `3` since the minimum is `2` and it occurs three times.

Count minimum cost in array

Snapchat

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Snapchat Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string