Skip to content

927. Three Equal Parts 👍

  • Time:
  • Space: 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
 public:
  vector<int> threeEqualParts(vector<int>& arr) {
    const int ones = ranges::count_if(arr, [](int a) { return a == 1; });

    if (ones == 0)
      return {0, static_cast<int>(arr.size()) - 1};
    if (ones % 3 != 0)
      return {-1, -1};

    int k = ones / 3;
    int i;
    int j;
    int first;
    int second;
    int third;

    for (i = 0; i < arr.size(); ++i)
      if (arr[i] == 1) {
        first = i;
        break;
      }

    int gapOnes = k;

    for (j = i + 1; j < arr.size(); ++j)
      if (arr[j] == 1 && --gapOnes == 0) {
        second = j;
        break;
      }

    gapOnes = k;

    for (i = j + 1; i < arr.size(); ++i)
      if (arr[i] == 1 && --gapOnes == 0) {
        third = i;
        break;
      }

    while (third < arr.size() && arr[first] == arr[second] &&
           arr[second] == arr[third]) {
      ++first;
      ++second;
      ++third;
    }

    if (third == arr.size())
      return {first - 1, second};
    return {-1, -1};
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
  public int[] threeEqualParts(int[] arr) {
    int ones = 0;

    for (final int a : arr)
      if (a == 1)
        ++ones;

    if (ones == 0)
      return new int[] {0, arr.length - 1};
    if (ones % 3 != 0)
      return new int[] {-1, -1};

    int k = ones / 3;
    int i = 0;
    int j = 0;
    int first = 0;
    int second = 0;
    int third = 0;

    for (i = 0; i < arr.length; ++i)
      if (arr[i] == 1) {
        first = i;
        break;
      }

    int gapOnes = k;

    for (j = i + 1; j < arr.length; ++j)
      if (arr[j] == 1 && --gapOnes == 0) {
        second = j;
        break;
      }

    gapOnes = k;

    for (i = j + 1; i < arr.length; ++i)
      if (arr[i] == 1 && --gapOnes == 0) {
        third = i;
        break;
      }

    while (third < arr.length && arr[first] == arr[second] && arr[second] == arr[third]) {
      ++first;
      ++second;
      ++third;
    }

    if (third == arr.length)
      return new int[] {first - 1, second};
    return new int[] {-1, -1};
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution:
  def threeEqualParts(self, arr: list[int]) -> list[int]:
    ones = sum(a == 1 for a in arr)

    if ones == 0:
      return [0, len(arr) - 1]
    if ones % 3 != 0:
      return [-1, -1]

    k = ones // 3
    i = 0

    for i in range(len(arr)):
      if arr[i] == 1:
        first = i
        break

    gapOnes = k

    for j in range(i + 1, len(arr)):
      if arr[j] == 1:
        gapOnes -= 1
        if gapOnes == 0:
          second = j
          break

    gapOnes = k

    for i in range(j + 1, len(arr)):
      if arr[i] == 1:
        gapOnes -= 1
        if gapOnes == 0:
          third = i
          break

    while third < len(arr) and arr[first] == arr[second] == arr[third]:
      first += 1
      second += 1
      third += 1

    if third == len(arr):
      return [first - 1, second]
    return [-1, -1]