Formatted question description: https://leetcode.ca/all/838.html

838. Push Dominoes

Level

Medium

Description

There are N dominoes in a line, and we place each domino vertically upright.

In the beginning, we simultaneously push some of the dominoes either to the left or to the right.

Image text

After each second, each domino that is falling to the left pushes the adjacent domino on the left.

Similarly, the dominoes falling to the right push their adjacent dominoes standing on the right.

When a vertical domino has dominoes falling on it from both sides, it stays still due to the balance of the forces.

For the purposes of this question, we will consider that a falling domino expends no additional force to a falling or already fallen domino.

Given a string “S” representing the initial state. S[i] = 'L', if the i-th domino has been pushed to the left; S[i] = 'R', if the i-th domino has been pushed to the right; S[i] = '.', if the i-th domino has not been pushed.

Return a string representing the final state.

Example 1:

Input: “.L.R…LR..L..”

Output: “LL.RR.LLRRLL..”

Example 2:

Input: “RR.L”

Output: “RR.L”

Explanation: The first domino expends no additional force on the second domino.

Note:

0 <= N <= 10^5
String dominoes contains only 'L', 'R' and '.'

Solution

First, collect all the indices of character 'L' and character 'R', using negative and positive indices respectively.

Next, deal with dominoes with the collected indices.

Among the collected indices, if the leftmost index is negative, then the dominoes left to the index all become 'L'. If the rightmost index is positive, then the dominoes right to the index all become 'R'.

For the remaining collected indices, consider each adjacent indices pair. If the left index is zero or positive and the right index is negative, then the dominoes between the two indices are pushed in two directions, and the middle index should be considered. Otherwise, the dominoes between the two indices are pushed in the same direction.

class Solution {
    public String pushDominoes(String dominoes) {
        char[] array = dominoes.toCharArray();
        int length = array.length;
        List<Integer> indices = new ArrayList<Integer>();
        for (int i = 0; i < length; i++) {
            char c = array[i];
            if (c == 'L')
                indices.add(-i);
            else if (c == 'R')
                indices.add(i);
        }
        int size = indices.size();
        if (size == 0)
            return dominoes;
        int firstIndex = indices.get(0), lastIndex = indices.get(size - 1);
        if (firstIndex < 0) {
            for (int i = -firstIndex - 1; i >= 0; i--)
                array[i] = 'L';
        }
        if (lastIndex >= 0) {
            if (lastIndex > 0 || array[0] == 'R') {
                for (int i = lastIndex + 1; i < length; i++)
                    array[i] = 'R';
            }
        }
        for (int i = 1; i < size; i++) {
            int index1 = indices.get(i - 1), index2 = indices.get(i);
            if (index1 >= 0 && array[index1] == 'R' && index2 < 0) {
                index2 = Math.abs(index2);
                if (index1 % 2 == index2 % 2) {
                    int mid = (index2 - index1) / 2 + index1;
                    for (int j = index1 + 1; j < mid; j++)
                        array[j] = 'R';
                    for (int j = index2 - 1; j > mid; j--)
                        array[j] = 'L';
                } else {
                    int midLeft = (index2 - index1) / 2 + index1;
                    for (int j = index1 + 1; j <= midLeft; j++)
                        array[j] = 'R';
                    for (int j = index2 - 1; j > midLeft; j--)
                        array[j] = 'L';
                }
            } else if (index1 >= 0 && array[index1] == 'R') {
                for (int j = index1 + 1; j < index2; j++)
                    array[j] = 'R';
            } else if (index2 < 0) {
                for (int j = -index1 + 1; j < -index2; j++)
                    array[j] = 'L';
            }
        }
        return new String(array);
    }
}

// OJ: https://leetcode.com/problems/push-dominoes/
// Time: O(N)
// Space: O(N)
class Solution {
public:
    string pushDominoes(string s) {
        int N = s.size();
        vector<int> v(N);
        for (int i = 0; i < N; ++i) {
            if (s[i] == 'L') {
                for (int j = i - 1; j >= 0 && s[j] != 'L'; --j) {
                    if (s[j] == 'R' && v[j] <= i - j) {
                        if (v[j] == i - j) s[j] = '.';
                        break;
                    }
                    s[j] = 'L';
                    v[j] = i - j;
                }
            } else if (s[i] == 'R') {
                if (v[i] != 0) continue;
                for (int j = i + 1; j < N && s[j] == '.'; ++j) {
                    s[j] = 'R';
                    v[j] = j - i;
                }
            }
        }
        return s;
    }
};

class Solution:
    def pushDominoes(self, dominoes: str) -> str:
        n = len(dominoes)
        q = deque()
        time = [-1] * n
        force = defaultdict(list)
        for i, f in enumerate(dominoes):
            if f != '.':
                q.append(i)
                time[i] = 0
                force[i].append(f)
        ans = ['.'] * n
        while q:
            i = q.popleft()
            if len(force[i]) == 1:
                ans[i] = f = force[i][0]
                j = i - 1 if f == 'L' else i + 1
                if 0 <= j < n:
                    t = time[i]
                    if time[j] == -1:
                        q.append(j)
                        time[j] = t + 1
                        force[j].append(f)
                    elif time[j] == t + 1:
                        force[j].append(f)
        return ''.join(ans)

############

class Solution(object):
    def pushDominoes(self, d):
        """
        :type dominoes: str
        :rtype: str
        """
        d = "L" + d + "R"
        res = []
        l = 0
        for r in range(1, len(d)):
            if d[r] == '.':
                continue
            mid = r - l - 1
            if l:
                res.append(d[l])
            if d[l] == d[r]:
                res.append(d[l] * mid)
            elif d[l] == 'L' and d[r] == 'R':
                res.append('.' * mid)
            else:
                res.append('R' * (mid // 2) + '.' * (mid % 2) + 'L' * (mid // 2))
            l = r
        return "".join(res)

func pushDominoes(dominoes string) string {
	n := len(dominoes)
	q := []int{}
	time := make([]int, n)
	for i := range time {
		time[i] = -1
	}
	force := make([][]byte, n)
	for i, c := range dominoes {
		if c != '.' {
			q = append(q, i)
			time[i] = 0
			force[i] = append(force[i], byte(c))
		}
	}

	ans := bytes.Repeat([]byte{'.'}, n)
	for len(q) > 0 {
		i := q[0]
		q = q[1:]
		if len(force[i]) > 1 {
			continue
		}
		f := force[i][0]
		ans[i] = f
		j := i - 1
		if f == 'R' {
			j = i + 1
		}
		if 0 <= j && j < n {
			t := time[i]
			if time[j] == -1 {
				q = append(q, j)
				time[j] = t + 1
				force[j] = append(force[j], f)
			} else if time[j] == t+1 {
				force[j] = append(force[j], f)
			}
		}
	}
	return string(ans)
}

function pushDominoes(dominoes: string): string {
    const n = dominoes.length;
    const map = {
        L: -1,
        R: 1,
        '.': 0,
    };
    let ans = new Array(n).fill(0);
    let visited = new Array(n).fill(0);
    let queue = [];
    let depth = 1;
    for (let i = 0; i < n; i++) {
        let cur = map[dominoes.charAt(i)];
        if (cur) {
            queue.push(i);
            visited[i] = depth;
            ans[i] = cur;
        }
    }
    while (queue.length) {
        depth++;
        let nextLevel = [];
        for (let i of queue) {
            const dx = ans[i];
            let x = i + dx;
            if (x >= 0 && x < n && [0, depth].includes(visited[x])) {
                ans[x] += dx;
                visited[x] = depth;
                nextLevel.push(x);
            }
        }
        queue = nextLevel;
    }
    return ans
        .map(d => {
            if (!d) return '.';
            else if (d < 0) return 'L';
            else return 'R';
        })
        .join('');
}

838 - Push Dominoes

838. Push Dominoes

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

838. Push Dominoes

Level

Description

Solution

All Problems

All Solutions