CodingBison

Let us go through some of the common problems related to arrays. Note that arrays are a general structure and will show up as we see more strategies in future sections.

Problem: Remove Duplicates and Compress a Sorted Array

We are given an integer arr sorted in increasing order, and we have to remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Thus, we need to unique shift elements on the left. Once all unique elements are shifted to the left, we need to reset the right subarray to 0.

Examples:

If arr is [1, 2, 2, 2], then we should return [1, 2, 0, 0]

If arr is [1, 2, 3, 4], then we should return [1, 2, 3, 4]

Solution:

The basic technique here is to traverse the array (arr) and track the number of duplicates. Think of this as tracking blanks (build a bubble with growing blank spaces). If you see an element that is same as the previous element, then increase the blank count. Otherwise, shift the element by blank spaces on the left. Once you are done, reset the last blank_count elements to 0.

 void solution(int arr[], int len) {
    int blank_counts = 0;

     for (int i = 1; i < arr.length; i++) {
         if (arr[i] == arr[i-1]) {
             blank_counts++;
         } else {
             arr[i-blank_counts] = arr[i];
         }
     }
     for (int i = 0; i < blank_counts; i++) {
         arr[arr.length - 1 - i] = 0;
     }
 }

Problem: Remove Duplicates but keep one Duplicate and Compress a Sorted Array

Let us modify the above problem of "Remove Duplicates from Sorted Array but keep one Duplicate" so that instead of having unique elements only once, they can be allowed in the resulting array twice. Thus, if we have an array of [1, 1, 1, 1, 1], then instead of returning [1, 0, 0, 0, 0] (as in the earlier problem), now we would need to return [1, 1, 0, 0, 0].

A variant of this problem is in LeetCode: https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

Examples:

If arr is [1, 2, 2, 2], then we should return [1, 2, 2, 0]

If arr is [1, 1, 1, 1, 2, 2, 2, 3], then we should return [1, 1, 2, 2, 3, 0, 0, 0]

Solution:

For this problem, we keep the same solution as above but modify it by keeping a variable to keep the count of the dup of the current number. As long as the current element (arr[i]) in the array is same as previous, we increase the dup or else reset it to 0. Further, only if duplicate is more than 1, we increase the blank_counts.

 void solution(int arr[]) {
     if (arr.length  == 0) return;

     int i = 0, blank_counts = 0, dup = 0, prev = arr[0];

     for (i = 1; i < arr.length; i++) {
         dup = (arr[i] == prev) ? dup + 1: 0;
         if (dup > 1) {
             blank_counts++;
         } else {
             arr[i-blank_counts] = arr[i];
         }
         prev = arr[i];
     }

     for (i = 0; i < blank_counts; i++) {
         arr[arr.length - 1 - i] = 0;
     }
 }