Data Structures & Algorithms In Go/

...

/

Solution Review: Partitioning of 0s and 1s

Solution Review: Partitioning of 0s and 1s

Let's look at the solution to the challenge posed in the previous lesson.

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

Press + to interact
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 ...