Blogs Hub

Check If It Is a Straight Line - Array - Easy - LeetCode - MiniTV

Check If It Is a Straight Line - Array - Easy - LeetCode - मिनी टीवी

You are given an array coordinates, coordinates[i] = [x, y], where [x, y] represents the coordinate of a point. Check if these points make a straight line in the XY plane.

 

Example 1:

Input: coordinates = [[1,2],[2,3],[3,4],[4,5],[5,6],[6,7]]

Output: true

 

Example 2:

Input: coordinates = [[1,1],[2,2],[3,4],[4,5],[5,6],[7,7]]

Output: false

 

Constraints:

2 <= coordinates.length <= 1000

coordinates[i].length == 2

-10^4 <= coordinates[i][0], coordinates[i][1] <= 10^4

coordinates contains no duplicate point.

 

Solution:

using System;
using System.Collections.Generic;
using System.Text;

namespace LeetCode.AskGif.Easy.Array
{
    public class CheckStraightLineSoln
    {
        public bool CheckStraightLine(int[][] coordinates)
        {
            double m = 0;
            double c = 0;
            
            if(coordinates.Length == 0)
            {
                return false;
            }

            if(coordinates.Length == 1 || coordinates.Length == 2)
            {
                return true;
            }
            
            //Equation of Line y = mx + c
            //Let's find value for m and c;
            //y1 = mx1 + c
            //y2 = mx2 + c
            //y2 - y1 = m(x2 - x1);

            var x1 = coordinates[0][0];
            var x2 = coordinates[1][0];
            var y1 = coordinates[0][1];
            var y2 = coordinates[1][1];

            if((x2-x1) == 0)            
            {
                //check if all x is same;
                for (int i = 2; i < coordinates.Length; i++)
                {
                    if(x1 != coordinates[i][0])
                    {
                        return false;
                    };
                }
                return true;
            }

            m = (double)(y2 - y1) / (x2 - x1);
            c = y1 - m * x1;

            for (int i = 2; i < coordinates.Length; i++)
            {
                if(coordinates[i][1] != m * coordinates[i][0] + c)
                {
                    return false;
                }
            }

            return true;
        }
    }
}

 

Time Complexity: O(n)

Space Complexity: O(1)

 

Unit Tests:

using LeetCode.AskGif.Easy.Array;
using Microsoft.VisualStudio.TestTools.UnitTesting;
using System;
using System.Collections.Generic;
using System.Text;

namespace CodingUnitTest.Easy.Array
{
    [TestClass]
    public class CheckStraightLineSolnTests
    {
        [TestMethod]
        public void CheckStraightLineSoln_First()
        {
            var coordinates = new int[,] {
                    { 1, 2 },
                    { 2, 3 },
                    { 3, 4 },
                    { 4, 5 },
                    { 5, 6 },
                    { 6, 7 }
                };            
            var output = true;

            var res = new CheckStraightLineSoln().CheckStraightLine(ArrayMapper(coordinates));

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void CheckStraightLineSoln_Second()
        {
            var coordinates = new int[,] {
                    { 1, 1 },
                    { 2, 2 },
                    { 3, 4 },
                    { 4, 5 },
                    { 5, 6 },
                    { 7, 7 }
                };
            var output = false;

            var res = new CheckStraightLineSoln().CheckStraightLine(ArrayMapper(coordinates));

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void CheckStraightLineSoln_Third()
        {
            var coordinates = new int[,] {
                    { 0, 0 },
                    { 0, 1 },
                    { 0, -1 }
                };
            var output = true;

            var res = new CheckStraightLineSoln().CheckStraightLine(ArrayMapper(coordinates));

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void CheckStraightLineSoln_Fourth()
        {
            var coordinates = new int[,] {
                    { 2, 1 },
                    { 4, 2 },
                    { 6, 3 }
                };
            var output = true;

            var res = new CheckStraightLineSoln().CheckStraightLine(ArrayMapper(coordinates));

            Assert.AreEqual(output, res);
        }

        private int[][] ArrayMapper(int[,] matrix)
        {
            var arr = new int[matrix.GetLength(0)][];
            for (int i = 0; i < matrix.GetLength(0); i++)
            {
                arr[i] = new int[matrix.GetLength(1)];
                for (int j = 0; j < matrix.GetLength(1); j++)
                {
                    arr[i][j] = matrix[i, j];
                }
            }

            return arr;
        }
    }
}