Valid Boomerang Leetcode Solution

Table of Contents

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 Solution

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:

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

(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

Initialize dx1 = difference of x-coordinates of the first two points and dy1 = difference of y-coordinates of first two points
Similarly, store dx2 = difference of y-coordinates of the last two points and dy2 = difference of y-coordinates of last two points
Return if ((dx1 * dy2) != (dx2 * dy1)) (the slope test condition)
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