Algorithm to consolidate (filter) an array

The problem this algorithm solves goes by many names. I call it consolidate. It is sometimes described as filtering an array or keeping matching elements. It is sometimes presented as removing matching elements. It may not be immediately obvious that a problem reduces to or otherwise benefits from the use of a standard algorithm, including this one.

We have an array of values. We want to keep those values in the array that match a given criteria. All retained values are moved to the beginning of the array. The remaining positions in the array store a special value (often 0 or null).

Example with String[]

public static void keepStartsWithLowercaseLetter(String[] arr)

Method keepStartsWithLowercaseLetter keeps all values in arr that start with a lowercase letter, consolidated to the left in arr. Positions in arr after the last retained String store null.

String[] arr = {"2 fish", "hamster", "goat", "6"};
keepStartsWithLowercaseLetter(arr);
System.out.println(Arrays.toString(arr));
// prints: [hamster, goat, null, null]

Example with int[]

public static void removeNegatives(int[] nums)

Method removeNegatives removes all values from nums that are less than 0. Retained values are consolidated to the left in nums. Positions in nums after the last remaining value store 0. (In this case, 0 is also a possible retained value.)

int[] nums = {5, -3, 8, 4, -2, 6};
removeNegatives(nums);
System.out.println(Arrays.toString(nums));
// prints: [5, 8, 4, 6, 0, 0]

Algorithm

  1. Store the position at which the next retained value would be placed. Initialize the position to the first possible position in the array.
  2. Loop through the array.
  3. If the current value in the array should be retained, copy it to the position from Step 1. Update the position to the next valid position.
  4. Loop through all remaining positions in the array. Set each position to the desired value.

keepStartsWithLowercaseLetter method

public static void keepStartsWithLowercaseLetter(String[] arr)
{
    int nextIndex = 0;
    
    for(int i = 0; i < arr.length; i++)
    {
        if(arr[i].compareTo("a") >=  0 && arr[i].compareTo("z") <= 0)
        {
            arr[nextIndex] = arr[i];
            nextIndex++;
        }
    }
    
    for(int i = nextIndex; i < arr.length; i++)
        arr[i] = null;
}

removeNegatives method

public static void removeNegatives(int[] nums)
{
    int nextIndex = 0;
    
    for(int i = 0; i < nums.length; i++)
    {
        if(nums[i] >= 0)
        {
            nums[nextIndex] = nums[i];
            nextIndex++;
        }
    }
    
    for(int i = nextIndex; i < nums.length; i++)
        nums[i] = 0;
}

Although this method is described as removing negatives, it can be easily thought of as retaining non-negatives. This allows the use of the standard algorithm.

Variation with a new array

public static int[] getNonNegatives(int[] nums)
{
    int[] nonNegatives = new int[nums.length];
    
    int nextIndex = 0;
    
    for(int i = 0; i < nums.length; i++)
    {
        if(nums[i] >= 0)
        {
            nonNegatives[nextIndex] = nums[i];
            nextIndex++;
        }
    }
    
    return nonNegatives;
}

This variation returns a new array containing the non-negatives values in nums.

int[] nums = {5, -3, 8, 4, -2, 6};
int[] nonNegs = getNonNegatives(nums);
System.out.println(Arrays.toString(nonNegs));
// prints: [5, 8, 4, 6, 0, 0]

The algorithm is nearly identical. Each retained element is copied to nonNegatives[nextIndex] instead of to nums[index].

If the default value of each value in the new array is the desired value for unused positions, the second loop from the original algorithm can be omitted.

With a 2D array

There are 2 ways this can be done with a 2D array.

The rows can be consolidated, as in 2021 A FR #4 ArrayResizer. 2021 FR PDF / ArrayResizer solution

The values within the 2D array can be consolidated. See consolidate in my 2D array exercises.

Practice standard algorithms with with AP CS Tutor Brandon Horn.

Selected AP CS A FR that request consolidation

Other examples from common resources

Help & comments

Get help from AP CS Tutor Brandon Horn

Comment on Consolidating an array