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

- Store the position at which the next retained value would be placed. Initialize the position to the first possible position in the array.
- Loop through the array.
- 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.
- 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

- 2021 A FR #4 ArrayResizer: 2021 FR PDF / ArrayResizer solution
- 2012 A FR #3 HorseBarn: 2012 FR PDF / HorseBarn solution