## DEV Community is a community of 852,088 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Wenqi Jiang

Posted on

# Description

Given a list of strings `strs`, containing the strings `"red"``"green"` and `"blue"`, partition the list so that the red come before green, which come before blue.

This should be done in O(n) time.

Bonus: Can you do it in O(1) space? That is, can you do it by only rearranging the list (i.e. without creating any new strings)?

Constraints:

• `n ≤ 100,000` where `n` is the length of `strs`.

## Example 1

### Input

``````strs = ["green", "blue", "red", "red"]
``````

### Output

``````["red", "red", "green", "blue"]
``````

two pointers

# Implementation

``````import java.util.*;

class Solution {
public String[] solve(String[] strs) {
int redIndex = 0, greenIndex = 0, blueIndex = strs.length - 1;
while (greenIndex <= blueIndex) {
switch (strs[greenIndex]) {
case "red":
swap(redIndex++, greenIndex++, strs);
break;
case "blue":
swap(blueIndex--, greenIndex, strs);
break;
default:
greenIndex++;
}
}
return strs;
}

private void swap(int i, int j, String[] strs) {
String temp = strs[i];
strs[i] = strs[j];
strs[j] = temp;
}
}
``````

• Time: O(n)
• Space: O(1)