LeetCode 858: Mirror Reflection Explained with Room Expansion and LCM

By Long Luo

This article is the solution What If the Ray Not Reflected and Expand the Room with Image Explanation of Problem 858. Mirror Reflection .

The key insight of this problem is that we do not need to simulate the reflections. Instead, imagine that every mirrored wall is connected to another identical room. The laser ray never changes direction—it simply travels through an infinitely expanded world.

This geometric transformation converts the problem into finding the first meeting point, which can be solved elegantly using LCM and GCD.

Intuition

What if we assume the Ray Not Reflected and Keeps Going?

Consider that there is a mirrored world behind the mirror, we can expand the room behind the mirror. The ray has not been reflected and keep going cross the room.

As the image below shows, we can easily know which receptor will the ray will meet first.

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

class Solution {
    public int mirrorReflection(int p, int q) {
        if (p == q) {
            return 1;
        }

        if (q == 0) {
            return 0;
        }

        int lcm = p * q / gcd(p, q);
        int x = lcm / p;
        int y = lcm / q;

        if (x % 2 == 1 && y % 2 == 1) {
            return 1;
        } else if (x % 2 == 0 && y % 2 == 1) {
            return 0;
        } else {
            return 2;
        }
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

Analysis

• Time Complexity: \(O(\log (max(p, q)))\)
• Space Complexity: \(O(1)\)

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗