Sort Items by Risk Severity

TCS NQT Coding Easy Go Ad-Free - ₹20/mo

Airport security officials have confiscated several items from passengers at the security checkpoint. All the items have been dumped into a huge box (represented as an array). Each item has a certain amount of risk, categorized as 0, 1, or 2. Your task is to sort the items based on their risk severity values, which range from 0 to 2.

Examples:

Input:
7
[1, 0, 2, 0, 1, 0, 2]

Output:
0 0 0 1 1 2 2

Input:
5
[2, 1, 0, 1, 2]

Output:
0 1 1 2 2

Input:
3
[0, 0, 0]

Output:
0 0 0

Constraints

1 <= N <= 1000
0 <= arr[i] <= 2

Editorial

Intuition:

Since the items only have three possible risk values (0, 1, 2), we can efficiently sort by counting occurrences of each value and then reconstructing the array in sorted order.

Approach:

Traverse the array once to count how many times 0, 1, and 2 appear.
Overwrite the original array: first fill with all 0s, then all 1s, then all 2s based on the counts.

class Solution {
public:
    void sortItems(int N, vector& arr) {
        int count0 = 0, count1 = 0, count2 = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] == 0) count0++;
            else if (arr[i] == 1) count1++;
            else count2++;
        }
        int index = 0;
        for (int i = 0; i < count0; i++) arr[index++] = 0;
        for (int i = 0; i < count1; i++) arr[index++] = 1;
        for (int i = 0; i < count2; i++) arr[index++] = 2;
    }
};
class Solution {
    public void sortItems(int N, int[] arr) {
        int count0 = 0, count1 = 0, count2 = 0;
        for (int i = 0; i < N; i++) {
            if (arr[i] == 0) count0++;
            else if (arr[i] == 1) count1++;
            else count2++;
        }
        int index = 0;
        for (int i = 0; i < count0; i++) arr[index++] = 0;
        for (int i = 0; i < count1; i++) arr[index++] = 1;
        for (int i = 0; i < count2; i++) arr[index++] = 2;
    }
}
class Solution:
    def sort_items(self, N, arr):
        count0 = 0
        count1 = 0
        count2 = 0
        for num in arr:
            if num == 0:
                count0 += 1
            elif num == 1:
                count1 += 1
            else:
                count2 += 1
        index = 0
        for _ in range(count0):
            arr[index] = 0
            index += 1
        for _ in range(count1):
            arr[index] = 1
            index += 1
        for _ in range(count2):
            arr[index] = 2
            index += 1
class Solution {
    sortItems(N, arr) {
        let count0 = 0, count1 = 0, count2 = 0;
        for (let i = 0; i < N; i++) {
            if (arr[i] === 0) count0++;
            else if (arr[i] === 1) count1++;
            else count2++;
        }
        let index = 0;
        for (let i = 0; i < count0; i++) arr[index++] = 0;
        for (let i = 0; i < count1; i++) arr[index++] = 1;
        for (let i = 0; i < count2; i++) arr[index++] = 2;
    }
}

Complexity Analysis:

Time Complexity: O(N) - we make two linear passes over the array: one to count and one to overwrite.

Space Complexity: O(1) - only a few integer variables are used regardless of input size.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories