# Algorithm to consolidate an array

The problem this algorithm solves goes by many names. I call it consolidate. It is sometimes called keep matching. It is sometimes presented as remove matching. 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.