Valid Boomerang Leetcode Solution  

Difficulty Level Easy
Frequently asked in Google
algorithms coding Interview interviewprep LeetCode LeetCodeSolutions Math

Problem Statement  

In this problem, we are given a set of three points in an X-Y 2-D plane. We need to return whether they form a boomerang or not, that is whether they are any three distinct points and do not form a straight line.

Example

Points = {{1 , 2} , {2 , 6} , {1 , 2}}
false
Points = {{1 , 1} , {2 , 3} , {6 , 7}}
true

The first input has two same points out of 3, so it is not a valid boomerang and we print false. The second test has 3 distinct points that do not form a straight line and we print true.

Valid Boomerang Leetcode SolutionPin

Approach(Slope Test)  

In the problem Check If It is a Straight Line, we have learnt that three distinct points are only collinear if the slope of the line formed by every pair of points is the same. Here, we need to check:

Please click Like if you loved this article?

  • If points are distinct
  • the points do not lie on a straight line

If any pair of points is the same, then the given input will pass the collinearity test, as any 2 points(or a single point) are always collinear. So, we just need to check for the equality of slopes. Note that if any three points, P1, P2 and P3 are collinear, we have

See also
Sum of minimum and maximum elements of all subarrays of size k

(y2 – y1) : (x2 – x1) :: (y3 – y2) : (x3 – x2) , or

(y2 – y1) * (x3 – x2) = (x2 – x1) * (y3 – y2)

where x1, x2, x3, y1, y2, y3 are the corresponding x and t coordinates of P1, P2 and P3.

Algorithm

  1. Initialize dx1 = difference of x-coordinates of the first two points and dy1 = difference of y-coordinates of first two points
  2. Similarly, store dx2 = difference of y-coordinates of the last two points and dy2 = difference of y-coordinates of last two points
  3. Return if ((dx1 * dy2) != (dx2 * dy1)) (the slope test condition)
  4. Print the result

Implementation of Valid Boomerang Leetcode Solution

C++ Program

#include <bits/stdc++.h>
using namespace std;

bool isBoomerang(vector <vector <int> > &points)
{
    int dx1 = (points[1][0] - points[0][0]);
    int dy1 = (points[1][1] - points[0][1]);
    int dx2 = (points[2][0] - points[1][0]);
    int dy2 = (points[2][1] - points[1][1]);

    return (dx1 * dy2) != (dy1 * dx2);
}

int main()
{
    vector <vector <int> > points = {{1 , 1} , {2 , 3} , {6 , 7}};
    if(isBoomerang(points))
        cout << "true\n";
    else
        cout << "false\n";
    return 0;
}

Java Program

class valid_boomerang
{
    public static void main(String args[])
    {
        int[][] points = {{1 , 1} , {2 , 3} , {6 , 7}};
        if(isBoomerang(points))
            System.out.println("true");
        else
            System.out.println("false");
    }

    static boolean isBoomerang(int[][] points)
    {
        int dx1 = (points[1][0] - points[0][0]);
        int dy1 = (points[1][1] - points[0][1]);
        int dx2 = (points[2][0] - points[1][0]);
        int dy2 = (points[2][1] - points[1][1]);

        return (dx1 * dy2) != (dy1 * dx2);
    }
}
true

Complexity Analysis of Valid Boomerang Leetcode Solution

Time Complexity

O(1) as we perform a constant number of operations.

Space complexity

O(1) as we use constant memory space.

Please click Like if you loved this article?

2
Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh