algoadvance

Leetcode 1037. Valid Boomerang

Problem Statement:

Given an array points where points[i] = [xi, yi] represents a point on the X-Y plane, return true if these points form a boomerang (a set of three points that are not all on the same line). Otherwise, return false.

Clarifying Questions:

1. Input Size: Is it guaranteed that the input will always contain exactly three points?
   • Yes, the problem guarantees that the input will always have exactly three points.
2. Data Type: What are the ranges and types for the coordinates?
   • Each coordinate [xi, yi] is an integer.
3. Output Format: Should the output be strictly boolean?
   • Yes, the output should be a boolean value (true or false).

Strategy:

1. Understanding Collinearity: Three points ( (x1, y1) ), ( (x2, y2) ), and ( (x3, y3) ) are collinear if they lie on the same straight line. This happens if the slope between each pair of points is the same:
   • Slope between ( (x1, y1) ) and ( (x2, y2) ) is ( \frac{y2 - y1}{x2 - x1} )
   • Slope between ( (x1, y1) ) and ( (x3, y3) ) is ( \frac{y3 - y1}{x3 - x1} )
2. Avoid Division for Slope: To avoid division (and potential division by zero errors), we can use a cross-multiplication approach to determine collinearity:
   • Points are collinear if ( (y2 - y1) * (x3 - x1) = (y3 - y1) * (x2 - x1) )
3. Implementation: Calculate the left-hand side (LHS) and right-hand side (RHS) of the above equation and return false if they are equal (indicating collinearity) and true otherwise.

Java Code:

public class ValidBoomerang {
    public boolean isBoomerang(int[][] points) {
        int x1 = points[0][0], y1 = points[0][1];
        int x2 = points[1][0], y2 = points[1][1];
        int x3 = points[2][0], y3 = points[2][1];

        int lhs = (y2 - y1) * (x3 - x1);
        int rhs = (y3 - y1) * (x2 - x1);

        return lhs != rhs;
    }

    public static void main(String[] args) {
        ValidBoomerang vb = new ValidBoomerang();
        int[][] points1 = // use example from above
        int[][] points2 = // use example from above

        System.out.println(vb.isBoomerang(points1)); // true
        System.out.println(vb.isBoomerang(points2)); // false
    }
}

Time Complexity:

• Time Complexity: O(1)
  • The algorithm performs a constant number of arithmetic operations regardless of the input values. Therefore, it takes constant time.
• Space Complexity: O(1)
  • The algorithm uses a constant amount of space for variables to store the coordinates and intermediate calculations.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?