Search⌘ K
AI Features
Home
Courses
Data Structures & Algorithms In Go

Solution Review: Partitioning of 0s and 1s

Explore the partitioning algorithm that efficiently sorts arrays containing 0s and 1s using two pointers from each end. Understand the logic behind pointer movement, swapping, and how this approach achieves linear time complexity through step-by-step explanation and code illustration.

We'll cover the following...

Solution

We begin at both ends. The left end stores the start index and the right end stores the last index. We traverse from the left till we have 0s in the array. Then we traverse from the right till we have 1s in the end. Finally, we swap the two and follow the same process till the left is less than the right.

Let’s look at an illustration of the algorithm above.

Program

Go (1.6.2)
package main
import ("fmt")
func swap(x, y int) (int, int) {
    return y, x
}
func Partition01(arr []int, size int) { 
    left := 0
    right := size - 1
    count := 0
    for left < right {
        for arr[left] == 0 {
            left += 1
      }
        for arr[right] == 1 {
            right -= 1
      }
        if (left < right) {
            arr[left],arr[right] = swap(arr[left],arr[right])
            count += 1
      }
    }
    
}
// Testing code
func main() {
  arr := []int{ 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1 }
  Partition01(arr, len(arr))
  fmt.Println(arr)
  
}

Time complexity

Time complexity appears to ...