List Partitioning

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"]

---

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)