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,000wherenis the length ofstrs.
Example 1
Input
strs = ["green", "blue", "red", "red"]
Output
["red", "red", "green", "blue"]
Intuition
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 Complexity
- Time: O(n)
- Space: O(1)
Top comments (0)