Day 23 | Greedy | Sort Zero | C++

Sort Zero is a good greedy problem to practice implementation skills.

Let's understand the problem first

We can select any number and change all its occurrences to 0. In minimum steps, we need to make the array non-decreasing [Increasing order with allowed duplicates]

Let's make some observations

1. We cannot make zeros in the middle of two positive numbers like this 0 0 0 1 0 2 4 5 Reason - Array needs to be non-decreasing, thus will be only before positive numbers

2. All 0 comes in the prefix on only Prefix means some part of the array that starts from index 0 Example - Subarray (arr[0] to arr[i]) Reason - There are no negative elements and the array is non-decreasing

3. So the answer will be something like this [some zeros][then some non-decreasing sequence of positive integers] like 0 0 0 0 1 2 3

4. If we have prefix zeros till index i, then all elements that appear in arr[0] to arr[i] does not occur in range arr[i+1] to arr[n-1]

So we can make the array non-decreasing by making element till ith index 0 if the following are true

1. For all elements in set {a[0] ... a[i]}, none of them appears in set {a[i+1]...a[n-1]}

2. a[i+1] ... a[n-1] is sorted

If we find the smallest i where the following condition holds true, then the answer is the count of unique elements in set{a[0] ... a[i]}

How to check For all elements in set {a[0] ... a[i]}, none of them appears in set {a[i+1]...a[n-1]}

Step 1

Let's keep a map last_index_of_element, which stores the last index of every value.

For example

arr = 4 3 2 1 1 2

last_index_of_element = {

1: 4,

2: 5,

4: 0,

3: 1

}

We can do it like this

for(int i = 0; i < n; i++){
    last_index_of_element[a[i]] = i;
}

Step 2

Calculate largest_index_of_included_elements such that largest_index_of_included_elements[i] = maximum last index of any value occuring till i

We can do it like this

for(int i = 0; i < n; i++){
        largest_index_of_included_elements[i] = last_index_of_element[a[i]];
        if(i > 0)
            largest_index_of_included_elements[i] =         
                   max(largest_index_of_included_elements[i-1], 
                          largest_index_of_included_elements[i]);
    }

Step 3

Calculate the smallest i, after which the suffix is sorted

We can do this like this

int from_where_suffix_is_sorted;
 for(from_where_suffix_is_sorted = n-1; from_where_suffix_is_sorted > 0; from_where_suffix_is_sorted--){
  if(a[from_where_suffix_is_sorted] < a[from_where_suffix_is_sorted - 1]){
            break;
        }   
    }

Now everything after from_where_suffix_is_sorted will be sorted so we need to check for point 1 only

We can calculate our answer like this

int prefix_zero_end_index = from_where_suffix_is_sorted - 1;
    //Now answer if possible only beyond this
    //Checking if we have not made anyother element zero between 
    //from_where_suffix_is_sorted to n-1
    while(prefix_zero_end_index < largest_index_of_included_elements[prefix_zero_end_index]){
        prefix_zero_end_index++;
    }
    //counting unique numbers till prefix_zero_end_index, as we need that     
    //many operations
    set<int> s;
    while(prefix_zero_end_index >= 0){
        s.insert(a[prefix_zero_end_index]);
        prefix_zero_end_index--;
    }
    cout << s.size() << "\n";

You can find a complete solution here

Please like and comment if you like my content