• ← Previous
• Next →

Let us go through some of the common problems related to arrays.

Intersection of Three Sorted Arrays

Problem: https://leetcode.com/problems/intersection-of-three-sorted-arrays/

This is a pretty cool problem. For this to work, the elements from all three arrays should be same. So, we fix arr1[i]. As long as arr2[j] and arr3[k] are less than arr1[i], we increment them. In the end, we check if all the three elements that are exposed (i, j, k) are same. If so, we add to the list.

 class Solution {
     public List<Integer> arraysIntersection(int[] arr1, int[] arr2, int[] arr3) {
         List<Integer> list = new ArrayList();

         int j = 0, k = 0;
         for (int i = 0; i < arr1.length; i++) {
             while (j < arr2.length &&  arr2[j] < arr1[i]) j++;
             while (k < arr3.length && arr3[k] < arr1[i]) k++;
             if (j < arr2.length && k < arr3.length)
                 if ((arr1[i] == arr2[j]) && (arr2[j] == arr3[k])) list.add(arr1[i]);
         }

         return list;
     }
 }

Remove Duplicates from Sorted Array

Problem: https://leetcode.com/problems/remove-duplicates-from-sorted-array/

The basic technique is to grow the bubble. 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.

 int remove_duplicate_from_sorted_array(int a[], int len) {
   int i = 0, blank_counts = 0;

   for (i = 1; i < len; i++) {
     if (a[i] == a[i-1]) {
         blank_counts++;
     } else {
         a[i-blank_counts] = a[i];
     }
   }
   for (i = 0; i < blank_counts; i++) {
     a[len - 1 - i] = 0;
   }
 }

Problem: https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

In Remove Duplicates from Sorted Array II, we need to keep a variable to keep the count of the dup.

 int removeDuplicates(int* a, int len) {
     int blanks = 0, dup = 0, i =1, prev;

     if (!len) return 0;

     prev = a[0];
     for (i = 1; i < len; i++) {
         dup = (a[i] == prev) ? dup + 1: 0;
         if (dup > 1) {
            blanks++;
         } else {
            a[i-blanks] = a[i];
         }
         prev = a[i];
     }

     return (len-blanks);
 }

• ← Previous
• Next →