Introduction

In this blog post, we will explore how to solve the LeetCode problem "2001" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You are given n rectangles represented by a 0-indexed 2D integer array rectangles, where rectangles[i] = [widthi, heighti] denotes the width and height of the ith rectangle. Two rectangles i and j (i < j) are considered interchangeable if they have the same width-to-height ratio. More formally, two rectangles are interchangeable if widthi/heighti == widthj/heightj (using decimal division, not integer division). Return the number of pairs of interchangeable rectangles in rectangles. Example 1: Input: rectangles = [[4,8],[3,6],[10,20],[15,30]] Output: 6 Explanation: The following are the interchangeable pairs of rectangles by index (0-indexed): - Rectangle 0 with rectangle 1: 4/8 == 3/6. - Rectangle 0 with rectangle 2: 4/8 == 10/20. - Rectangle 0 with rectangle 3: 4/8 == 15/30. - Rectangle 1 with rectangle 2: 3/6 == 10/20. - Rectangle 1 with rectangle 3: 3/6 == 15/30. - Rectangle 2 with rectangle 3: 10/20 == 15/30. Example 2: Input: rectangles = [[4,5],[7,8]] Output: 0 Explanation: There are no interchangeable pairs of rectangles. Constraints: n == rectangles.length 1 <= n <= 105 rectangles[i].length == 2 1 <= widthi, heighti <= 105

Explanation

Here's the solution to the problem:

• High-level approach:

  • Calculate the greatest common divisor (GCD) for each rectangle's width and height.
  • Simplify the width/height ratio by dividing both by their GCD. This ensures that rectangles with the same ratio, even if represented differently, will have the same simplified ratio.
  • Use a dictionary (hash map) to store the counts of each simplified ratio. Then, iterate through the dictionary and for each ratio, calculate the number of pairs of rectangles that have that ratio using the formula n*(n-1)/2 where n is the number of rectangles with that ratio. Sum up these pair counts.

• Complexity:

  • Runtime Complexity: O(n * log(max(width, height))), where n is the number of rectangles. The log factor comes from the GCD calculation.
  • Storage Complexity: O(n) in the worst case, where n is the number of rectangles. This happens if all rectangles have unique ratios.

Code

    from math import gcd

def interchangeableRectangles(rectangles):
    """
    Calculates the number of interchangeable pairs of rectangles.

    Args:
        rectangles: A list of lists, where each inner list represents a rectangle
                    with [width, height].

    Returns:
        The number of interchangeable pairs of rectangles.
    """

    ratio_counts = {}
    for width, height in rectangles:
        common_divisor = gcd(width, height)
        simplified_width = width // common_divisor
        simplified_height = height // common_divisor
        ratio = (simplified_width, simplified_height)  # Use tuple as dictionary key

        if ratio in ratio_counts:
            ratio_counts[ratio] += 1
        else:
            ratio_counts[ratio] = 1

    pair_count = 0
    for count in ratio_counts.values():
        pair_count += count * (count - 1) // 2

    return pair_count