Push Dominoes

Basically, for my solution of Push Dominoes, I did not want to back-track on any of the decisions that I made previously; meaning I wanted to swap-in the correct letters in just one-iteration.

To do this, I believed it was necessary to compute all the indices for the dominoes pushed Left, left_indices, and all the indices for the dominoes pushed Right, right_indices. I also added index 0 to the beginning of left_indices, and added index dominoes.size() to the end of right_indices.

Then, if you have an iterator, l iterating through left_indices and r iterating through right_indices, you have 3 possible outcomes:

• if left_indices[l] < right_indices[r], that implies that left_indices[l-1] < left_indices[l] < right_indices[r]
  • therefore, while this condition still holds, it means that all characters between index left_indices[l-1] and index left_indices[l] should be set to L. Then we can increment the index l, before checking if the while loop still holds.
  • we added index 0 to the beginning of left_indices and initialized l to 1 (to allow the algorithm set the first few indices to L if the conditions permit)
• if right_indices[r+1] < left_indices[l], that implies that right_indices[r] < right_indices[r+1] < left_indices[l]
  • therefore, while this condition still holds, it means that all characters between index left_indices[r] and index left_indices[r+1] should be set to R. Then we can increment the index r, before checking if the while loop still holds.
  • we added index dominoes.size() to the end of right_indices and initialized r to 0 for this reason (to allow the algorithm set the last few indices to R if the conditions permit)
• thus, we should be left with r and l such that right_indices[r] < left_indices[l] < right_indices[r+1]
  • then, we can iterate through the indices between right_indices[r] and left_indices[l], converting the relevant indices to L or R respectively

Finally, we break out of the while loop if l or r exceeds left_indices.size() or right_indices.size() respectively. However, if there exists r such that r < right_indices.size(), we can just iterate between right_indices[r] and dominoes.size() and set them all to R.

code

class Solution {
public:
    string pushDominoes(string dominoes) {
        vector<int> left_indices;
        left_indices.push_back(0);
        vector<int> right_indices;

        for (int i = 0; i < dominoes.size(); ++i) {
            if (dominoes[i] == 'L') {
                left_indices.push_back(i);
            } else if (dominoes[i] == 'R') {
                right_indices.push_back(i);
            }
        }
        right_indices.push_back(dominoes.size());

        int l = 1, r = 0;
        for (; l < left_indices.size() && r < right_indices.size();) {
            for (; l < left_indices.size() && left_indices[l] < right_indices[r];) {
                for (int i = left_indices[l-1]; i < left_indices[l]; ++i) {
                    dominoes[i] = 'L';
                }
                ++l;
            }

            for (; l < left_indices.size() && r+1 < right_indices.size() && right_indices[r+1] < left_indices[l];) {
                for (int i = right_indices[r]; i < right_indices[r+1]; ++i) {
                    dominoes[i] = 'R';
                }
                ++r;
            }

            if (l < left_indices.size() && r < right_indices.size() && right_indices[r] < left_indices[l]) {
                for (int i = 1; i < (left_indices[l]-right_indices[r]+1)/2; ++i) {
                    dominoes[left_indices[l]-i] = 'L';
                    dominoes[right_indices[r]+i] = 'R';
                }
                ++l;
                ++r;
            }
        }
        if (r < right_indices.size()) {
            for (int i = right_indices[r]+1; i < dominoes.size(); ++i) {
                dominoes[i] = 'R';
            }
        }
        return dominoes;
    }
};

complexity

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

time taken

• 20 minutes and 8 seconds (disaster)