Intuition

For each i, answer[i] is the sum of distances between box i and all “1” in boxes. answer[0] can be computed with 1-pass iteration. The key is to find the relationship between answer[i + 1] and answer[i] as we computing the answer from left to right.

Observation, when we move from box i to box i + 1:

• the distance to “1” on the left increased 1
• the distance to “1” on the right decreased 1

We just need to track the count of “1” on each side.

Approach

• left_ones: the count of “1” on the left (in range [0, i - 1])
• right_ones: the count of “1” on the right (in range [i, n - 1])
• dis_sum: the answer

Can solve the problem with two-pass.

Code

• Python3
• C++

• class Solution:
      def minOperations(self, boxes: str) -> List[int]:
          left_ones = right_ones = dis_sum = 0
          res = [-1] * len(boxes)
          for i, x in enumerate(boxes):
              if x == "1":
                  right_ones += 1
                  dis_sum += i
          for i, x in enumerate(boxes):
              res[i] = dis_sum
              if x == "1":
                  left_ones += 1
                  right_ones -= 1
              dis_sum = dis_sum + left_ones - right_ones
          return res
  

• class Solution {
  public:
      vector<int> minOperations(string boxes) {
          int left_ones = 0, right_ones = 0, dis_sum = 0, n = boxes.size();
          for (int i = 0; i < n; i++) {
              if (boxes[i] == '1') {
                  dis_sum += i;
                  right_ones++;
              }
          }
          vector<int> res(n, 0);
          for (int i = 0; i < n; i++) {
              res[i] = dis_sum;
              if (boxes[i] == '1') {
                  left_ones++, right_ones--;
              }
              dis_sum = dis_sum + left_ones - right_ones;
          }
          return res;
      }
  };
  

Complexity

• Time complexity: $O(N)$
• Space complexity: $O(1)$