[LeetCode] 2167. Minimum Time to Remove All Cars Containing Illegal Goods explained

Problem

2167. Minimum Time to Remove All Cars Containing Illegal Goods

Approach

Think of two pointers.

• left: minimum time to clear ‘1’s from s[0] to s[i]
• right: minimum time to clear ‘1’s from s[i+1] to s[n-1]

While iteratating from left to right,

update left value with minimum of those two:

• left+2 (cost of removing s[i] without removing prefix)
• i+1 (cost of removing prefix all the way to s[i])

update right value with:

• n - 1 - i (cost of removing all cars from the right)

Update ans during the iteration.

\[ans = \min_{\rm i} (left_i + right_i)\]

Code

/**
 * written: 2022. 02. 11. Fri. 16:57:01 [UTC+9]
 * jooncco의 mac에서.
 **/

class Solution {
public:
    int minimumTime(string s) {
        int n= s.length(), l= 0, ans= n;
        for (int i=0; i < n; ++i) {
            l= min(l + 2*(s[i] == '1'), i+1);
            ans= min(ans, l + n-1-i);
        }
        return ans;
    }
};

Complexity

• Time: \(O(n)\)
• Space: \(O(1)\)