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 make a boomerang, otherwise return false.

A boomerang is formed by three points that are all distinct and not in a straight line.

Example:

Input: points = [[1,1],[2,3],[3,2]]
Output: true

Input: points = [[1,1],[2,2],[3,3]]
Output: false

Clarifying Questions

  1. Can points be negative?
    • Yes, points can be any integer coordinates on the X-Y plane.
  2. Is it guaranteed that there are exactly three points?
    • Yes, the input array points always contains exactly three points.
  3. Do the points need to be distinct for a valid boomerang?
    • Yes, the points need to be distinct and must not be collinear.

Strategy

To determine if the three points form a boomerang, they should be distinct and not collinear. Three points are collinear if the area formed by them is zero. The area of a triangle formed by three points ((x1, y1)), ((x2, y2)), ((x3, y3)) can be determined via the determinant method: [ \text{Area} = \frac{1}{2} \left| x1(y2-y3) + x2(y3-y1) + x3(y1-y2) \right| ]

For the points to not be collinear, this area should not be equal to zero: [ x1(y2-y3) + x2(y3-y1) + x3(y1-y2) \neq 0 ]

Code

#include <vector>
#include <cmath>

bool isBoomerang(std::vector<std::vector<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];
    
    return (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) != 0;
}

Time Complexity

The time complexity of this solution is constant, (O(1)), because it involves a fixed number of arithmetic operations irrespective of the input size. The space complexity is also (O(1)) as we are only using a few additional variables.

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