Mirror Reflection solution and explanation
Google
9 more videos on this problem
Mirror Reflection | Live Coding with Explanation | Leetcode - 858Algorithms Made Easy · 5:32 · 9K views
Leetcode 858 Mirror Reflection | Maths Geometry | SDE Preparation SheetCoding Decoded · 7:54 · 3K views
LeetCode 858. Mirror ReflectionHappy Coding · 13:58 · 2K views
LeetCode 858. Mirror Reflection - Nov 17th - November LeetCoding Challenge - GoMaster.inGoMaster Coding Interviews · 12:32 · 1K views
Daily Leetcode #856: Aug 04, 2022 - 858. Mirror ReflectionProgramming Live with Larry · 30:13 · 965 views
Facebook Coding Interview Question | Leetcode 858 | Mirror ReflectionWorkWithGoogler · 12:46 · 505 views
858. Mirror Reflection (Updated Video in Description/Comments) (Leetcode Medium)Programming Live with Larry · 22:59 · 477 views
Mirror Reflection | Leetcode problem # 858 | Explanation(tamil) and code in pythonCode with Vasanth · 11:11 · 322 views
Mirror Reflection | Easy Explanation 🔥| LeetCode Solution 858Gantavya Malviya · 10:17 · 301 views
Daily Leetcode #231: Nov 17, 2020 - 858. Mirror ReflectionProgramming Live with Larry · 33:37 · 291 views
The problem
There is a special square room with mirrors on each of the four walls. Except for the southwest corner, there are receptors on each of the remaining corners, numbered 0, 1, and 2.
The square room has walls of length p and a laser ray from the southwest corner first meets the east wall at a distance q from the 0th receptor.
Given the two integers p and q, return the number of the receptor that the ray meets first.
The test cases are guaranteed so that the ray will meet a receptor eventually.
Example 1:
Input: p = 2, q = 1 Output: 2 Explanation: The ray meets receptor 2 the first time it gets reflected back to the left wall.
Example 2:
Input: p = 3, q = 1 Output: 1
Constraints:
1 <= q <= p <= 1000
Approach overview
Problem Overview: A laser starts from the southwest corner of a square room with mirrors on every wall. The beam travels toward the east wall and reflects perfectly. Given the room side length p and the vertical offset q, determine which receptor (0, 1, or 2) the beam hits first.
Approach 1: Iterative Simulation (O(p) time, O(1) space)
This method simulates the laser reflections step by step. Each time the beam reaches a vertical wall, it reflects and continues toward the opposite wall while maintaining the same slope. You track the vertical position after each horizontal traversal and flip direction whenever the beam hits the top or bottom boundary. The simulation stops once the beam lands exactly on one of the receptor corners. This approach mirrors the physical process and helps build intuition about the reflections, but it can require up to O(p) steps when p is large.
Approach 2: Mathematical Approach Using GCD (O(log n) time, O(1) space)
The key observation is that repeated reflections are equivalent to extending the room into mirrored copies and letting the beam travel in a straight line. The beam reaches a receptor when the vertical travel equals a multiple of p. This reduces the problem to finding the least common multiple of p and q. Compute lcm = p * q / gcd(p, q). The number of room extensions horizontally is lcm / p and vertically is lcm / q. Their parity determines the receptor: even horizontal extensions lead to receptor 2, odd horizontal with odd vertical leads to receptor 1, and odd horizontal with even vertical leads to receptor 0. The gcd computation makes the solution efficient and is a classic trick in number theory problems involving repeating patterns.
This reasoning converts a geometric reflection problem into pure arithmetic. Instead of simulating every bounce, you analyze how many room copies the beam effectively crosses. Concepts from math and geometry combine here: geometry explains the reflections, while number theory determines when the beam aligns with a receptor.
Recommended for interviews: The mathematical GCD approach is what interviewers expect. It demonstrates pattern recognition and the ability to convert geometry into arithmetic reasoning. The simulation approach shows understanding of the physical behavior, but the optimized math solution proves you can identify the hidden number theory insight.
Approach 1: Mathematical Approach Using GCD
This approach leverages the properties of the greatest common divisor (GCD). The ray will hit a receptor the first time it reaches a location where both the vertical and horizontal distances are multiples of the given dimensions of the square room.
Specifically, the ray's first encounter with a receptor will happen after k*step_x = multiple of p and k*step_y = multiple of q. The reflections allow us to simplify the problem into smaller parts which can be resolved by finding the lowest common multiple of the grid dimension.
import math
def mirrorReflection(p, q):
gcd = math.gcd(p, q)
p //= gcd
q //= gcd
if p % 2 == 0 and q % 2 == 1:
return 0
if p % 2 == 1 and q % 2 == 1:
return 1
if p % 2 == 1 and q % 2 == 0:
return 2
return -1
print(mirrorReflection(2, 1))public class Solution {
public int mirrorReflection(int p, int q) {
int gcd = gcd(p, q);
p /= gcd;
q /= gcd;
if (p % 2 == 0 && q % 2 == 1) return 0;
if (p % 2 == 1 && q % 2 == 1) return 1;
if (p % 2 == 1 && q % 2 == 0) return 2;
return -1;
}
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void main(String[] args) {
Solution sol = new Solution();
int result = sol.mirrorReflection(2, 1);
System.out.println(result);
}
}#include <iostream>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int mirrorReflection(int p, int q) {
int g = gcd(p, q);
p /= g;
q /= g;
if (p % 2 == 0 && q % 2 == 1) return 0;
if (p % 2 == 1 && q % 2 == 1) return 1;
if (p % 2 == 1 && q % 2 == 0) return 2;
return -1;
}
int main() {
int p = 2, q = 1;
cout << mirrorReflection(p, q) << endl;
return 0;
}function gcd(a, b) {
while (b !== 0) {
[a, b] = [b, a % b];
}
return a;
}
function mirrorReflection(p, q) {
const g = gcd(p, q);
p /= g;
q /= g;
if (p % 2 === 0 && q % 2 === 1) return 0;
if (p % 2 === 1 && q % 2 === 1) return 1;
if (p % 2 === 1 && q % 2 === 0) return 2;
return -1;
}
console.log(mirrorReflection(2, 1));#include <stdio.h>
int gcd(int a, int b) {
while (b != 0) {
int t = b;
b = a % b;
a = t;
}
return a;
}
int mirrorReflection(int p, int q) {
int g = gcd(p, q);
p /= g;
q /= g;
if (p % 2 == 0 && q % 2 == 1) return 0;
if (p % 2 == 1 && q % 2 == 1) return 1;
if (p % 2 == 1 && q % 2 == 0) return 2;
return -1; // This will never be reached due to the problem constraints
}
int main() {
int p = 2, q = 1;
printf("%d", mirrorReflection(p, q));
return 0;
}using System;
public class Solution {
public int MirrorReflection(int p, int q) {
int gcd = GCD(p, q);
p /= gcd;
q /= gcd;
if (p % 2 == 0 && q % 2 == 1) return 0;
if (p % 2 == 1 && q % 2 == 1) return 1;
if (p % 2 == 1 && q % 2 == 0) return 2;
return -1;
}
private int GCD(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MirrorReflection(2, 1));
}
}Python's built-in math.gcd function is used to determine the GCD. After simplifying the problem with GCD, we check the parity to return the correct recept
or number that the ray hits first.
Time Complexity: O(log(min(p, q))) due to the GCD calculation.
Space Complexity: O(1).
Approach 2: Iterative Simulation
This approach simulates the path of the light by extending the room along a grid infinitely. Each step checks whether the conditions for meeting a receptor are fulfilled. Although less efficient due to direct simulation, it provides a straightforward illustration of the problem dynamics.
def mirrorReflection(p, q):
m, n = 1, 1
while m * p != n * q:
n += 1
m = (n * q) // p
if m % 2 == 0 and n % 2 == 1:
return 0
if m % 2 == 1 and n % 2 == 1:
return 1
if m % 2 == 1 and n % 2 == 0:
return 2
return -1
print(mirrorReflection(2, 1))public class Solution {
public int mirrorReflection(int p, int q) {
int m = 1, n = 1;
while (m * p != n * q) {
n++;
m = (n * q) / p;
}
if (m % 2 == 0 && n % 2 == 1) return 0;
if (m % 2 == 1 && n % 2 == 1) return 1;
if (m % 2 == 1 && n % 2 == 0) return 2;
return -1;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.mirrorReflection(2, 1));
}
}This Python solution directly simulates the trajectory of the laser. The loop continues to increment the variables until the room's dimensions align, consistently checking whether the ray has reached a receptor or not.
Time Complexity: O(p / gcd(p, q))
Space Complexity: O(1).
Approach 3: Default Approach
function mirrorReflection(p: number, q: number): number {
const g = gcd(p, q);
p = Math.floor(p / g) % 2;
q = Math.floor(q / g) % 2;
if (p === 1 && q === 1) {
return 1;
}
return p === 1 ? 0 : 2;
}
function gcd(a: number, b: number): number {
return b === 0 ? a : gcd(b, a % b);
}func mirrorReflection(p int, q int) int {
g := gcd(p, q)
p = (p / g) % 2
q = (q / g) % 2
if p == 1 && q == 1 {
return 1
}
if p == 1 {
return 0
}
return 2
}
func gcd(a, b int) int {
if b == 0 {
return a
}
return gcd(b, a%b)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Mathematical Approach Using GCD | Time Complexity: O(log(min(p, q))) due to the GCD calculation. |
| Iterative Simulation | Time Complexity: O(p / gcd(p, q)) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Simulation | O(p) | O(1) | Useful for understanding the reflection mechanics or when constraints are small |
| Mathematical Approach Using GCD | O(log n) | O(1) | Optimal solution for large inputs; preferred in interviews and competitive programming |
Frequently asked questions
Is Mirror Reflection easy or hard?
Mirror Reflection is rated Medium on LeetCode but feels tricky because the reflection behavior hides a number theory pattern. Once you recognize that reflections can be modeled as straight-line movement across mirrored rooms, the solution becomes a short GCD-based calculation.
Mirror Reflection Python/Java solution
Most implementations compute gcd(p, q), derive the LCM relationship, and check parity conditions. Python solutions often use math.gcd, while Java implementations typically use a helper method for the Euclidean algorithm. The logic is identical across languages and runs in O(log n) time.
How to solve Mirror Reflection in O(log n)?
Use number theory instead of simulating reflections. Compute gcd(p, q) and derive lcm = p * q / gcd(p, q). The beam reaches a receptor when the vertical distance equals the LCM. Check the parity of lcm/p and lcm/q to determine whether receptor 0, 1, or 2 is hit.
What is the best approach for Mirror Reflection?
The mathematical approach using the greatest common divisor (GCD) is the most efficient solution. By computing the least common multiple of p and q, you determine how many room extensions the laser effectively travels horizontally and vertically. The parity of these counts identifies which receptor is hit. This runs in O(log n) time due to the GCD computation and uses O(1) space.
Is Mirror Reflection asked at Google/Amazon/Meta?
Mirror Reflection represents the type of mathematical reasoning questions seen in technical interviews at companies like Google and Meta, especially for roles emphasizing algorithmic problem solving. The problem tests understanding of GCD, LCM, and converting geometry problems into arithmetic patterns.
What data structure is used in Mirror Reflection?
No specialized data structures are required. The optimal solution relies purely on arithmetic operations such as GCD and LCM from number theory. The simulation version only uses basic variables to track the beam position and direction.
What is the time complexity of Mirror Reflection?
The optimal GCD-based solution runs in O(log n) time because it relies on the Euclidean algorithm to compute the greatest common divisor of p and q. The space complexity is O(1). A direct simulation approach can take up to O(p) time since it may simulate many reflections before reaching a receptor.