Leetcode: Three Equal Parts

Three Equal Parts


<a href=”https://github.com/dennyzhang/code.dennyzhang.com/tree/master/problems/three-equal-parts“><img align=”right” width=”200″ height=”183″ src=”github.png” /></a>

Similar Problems:


Given an array A of 0s and 1s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.

If it is possible, return any [i, j] with i+1 < j, such that:

  • A[1], A[2], …, A[i] is the first part;
  • A[i+1], A[i+2], …, A[j-1] is the second part, and
  • A[j], A[j+1], …, A[A.length – 1] is the third part.
  • All three parts have equal binary value.

If it is not possible, return [-1, -1].

Note that the entire part is used when considering what binary value it represents. For example, [1,1,0] represents 6 in decimal, not 3. Also, leading zeros are allowed, so [0,1,1] and [1,1] represent the same value.

Example 1:

Input: [1,0,1,0,1]
Output: [0,3]

Example 2:

Input: [1,1,0,1,1]
Output: [-1,-1]

Note:

  1. 3 <= A.length <= 30000
  2. A[i] = 0 or A[i] = 1

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
// Blog link: https://code.dennyzhang.com/three-equal-parts
// Basic Ideas: Find the value from the last part
// Complexity: Time O(n), Space O(1)
func threeEqualParts(A []int) []int {
    count := 0
    for _, v := range A {
        if v == 1 { count++ }
    }
    if count%3 != 0 {
        return []int{-1, -1}
    }

    if count == 0 {
        return []int{0, 2}
    }

    c := 0
    index1, index2, index3 := -1, -1, -1
    for i, v := range A {
        if v == 1 { c++ }
        if index1 == -1 && c == 1 {
            index1 = i
        }
        if index2 == -1 && c == count/3+1 {
            index2 = i
        }
        if index3 == -1 && c == 2*count/3+1 {
            index3 = i
        }
    }
    for i := 0; i<len(A)-index3; i++ {
        i1, i2, i3 := index1+i, index2+i, index3+i
        if i1 >= index2 || i2>=index3 || A[i1] != A[i3] || A[i2] != A[i3] {
            return []int{-1, -1}
        }
    }
    return []int{index1+len(A)-1-index3, index2+len(A)-index3}
}

<div style=”overflow: hidden;”>

<div style=”float: left; padding: 5px”> <a href=”https://www.linkedin.com/in/dennyzhang001“><img src=”linkedin.png” alt=”linkedin” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://github.com/dennyzhang“><img src=”github.png” alt=”github” /></a></div>

<div style=”float: left; padding: 5px”><a href=”https://www.dennyzhang.com/slack” target=”_blank” rel=”nofollow”><img src=”slack.png” alt=”slack”/></a></div>

</div>

Footnotes:

[1]

DEFINITION NOT FOUND.

[2]

DEFINITION NOT FOUND.


Share It, If You Like It.

Leave a Reply

Your email address will not be published.