DEV Community

Cover image for List Partitioning
Wenqi Jiang
Wenqi Jiang

Posted on

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"]
Enter fullscreen mode Exit fullscreen mode

Output

["red", "red", "green", "blue"]
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity

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

Discussion (0)