How do you solve Mirror Reflection on LeetCode?

Mirror Reflection (LeetCode #858) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log(min(p, q))) time complexity and O(1) space complexity. Key insight: Understanding the geometry of reflections can simplify complex problems.

What is the brute force solution for Mirror Reflection?

The brute force approach for Mirror Reflection is Brute Force, with O(n²) time complexity and O(1) space complexity. We can simulate the path of the laser ray as it bounces off the walls. By calculating the distance it travels and checking which receptor it hits first, we can determine the answer. This method is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(log(min(p, q))).

What algorithm or data structure is used to solve Mirror Reflection?

Mirror Reflection uses the following concepts: Math, Geometry, Number Theory. The recommended patterns to study are: Geometry, Mathematical Properties, GCD.

What are the interview tips for Mirror Reflection?

Always consider edge cases and constraints provided in the problem. Think about the geometry involved in the problem; sometimes a visual representation helps. Practice explaining your thought process clearly, as communication is key in interviews.

What are common mistakes when solving Mirror Reflection?

Forgetting to check the parity of p and q after finding the GCD. Overcomplicating the problem by simulating reflections instead of using mathematical properties.

#858

Mirror Reflection

Medium

MathGeometryNumber TheoryGeometryMathematical PropertiesGCD

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(log(min(p, q)))
Space	O(1)	O(1)

💡

Intuition

Time O(log(min(p, q)))Space O(1)

Instead of simulating each reflection, we can use mathematical properties of the problem. The laser's path can be simplified using the greatest common divisor (GCD) to determine the first receptor it hits.

⚙️

Algorithm

3 steps

1Step 1: Calculate the greatest common divisor (gcd) of p and q.
2Step 2: Determine how many times the laser hits the walls before reaching a receptor using the formula: p/gcd(p, q) and q/gcd(p, q).
3Step 3: If p/gcd is even, it hits receptor 0; if q/gcd is even, it hits receptor 1; otherwise, it hits receptor 2.

solution.py10 lines

1import math
2
3def mirrorReflection(p: int, q: int) -> int:
4    gcd = math.gcd(p, q)
5    if (p // gcd) % 2 == 0:
6        return 0
7    elif (q // gcd) % 2 == 0:
8        return 1
9    else:
10        return 2

ℹ

Complexity note: The optimal approach is efficient because the GCD calculation runs in logarithmic time, making it much faster than simulating each reflection.

1Understanding the geometry of reflections can simplify complex problems.
2Using GCD can help in determining the path without simulating every step.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.