Blogs Hub

Distance Between Bus Stops - Array - Easy - LeetCode - MiniTV

Distance Between Bus Stops - Array - Easy - LeetCode - मिनी टीवी

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

 

Example 1:

Input: distance = [1,2,3,4], start = 0, destination = 1

Output: 1

Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

 

Example 2:

Input: distance = [1,2,3,4], start = 0, destination = 2

Output: 3

Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

 

Example 3:

Input: distance = [1,2,3,4], start = 0, destination = 3

Output: 4

Explanation: Distance between 0 and 3 is 6 or 4, the minimum is 4.

 

Constraints:

1 <= n <= 10^4

distance.length == n

0 <= start, destination < n

0 <= distance[i] <= 10^4

 

Solution:

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

namespace LeetCode.AskGif.Easy.Array
{
    public class DistanceBetweenBusStopsSoln
    {
        public int DistanceBetweenBusStops(int[] distance, int start, int destination)
        {            
            var clockwise = 0;
            bool clockwiseFound = false;

            var antiClockwise = 0;
            bool antiClockwiseFound = false;
            int i = start;
            int j = start;
            
            while (true)
            {
                i++;
                j--;

                if (i > distance.Length - 1)
                {
                    i = 0;
                }

                if (j < 0)
                {
                    j = distance.Length - 1;
                }

                if (i == destination)
                {
                    if ((i - 1) < 0)
                    {
                        clockwise += distance[distance.Length - 1];
                    }
                    else
                    {
                        clockwise += distance[i - 1];
                    }                    
                    clockwiseFound = true;
                }

                if( j == destination)
                {                    
                    antiClockwise += distance[j];                                                     
                    antiClockwiseFound = true;
                }

                if (!clockwiseFound)
                {
                    if ((i - 1) < 0)
                    {
                        clockwise += distance[distance.Length - 1];
                    }
                    else
                    {
                        clockwise += distance[i - 1];
                    }
                }

                if (!antiClockwiseFound)
                {                    
                    antiClockwise += distance[j];                    
                }  
                
                if(clockwiseFound && antiClockwiseFound)
                {
                    break;
                }
            }

            return clockwise < antiClockwise ? clockwise : antiClockwise;
        }
    }
}

 

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 DistanceBetweenBusStopsSolnTests
    {
        [TestMethod]
        public void DistanceBetweenBusStopsSoln_First()
        {
            var distance = new int[] { 1, 2, 3, 4 };
            var start = 0;
            var destination = 1;

            var output = 1;

            var res = new DistanceBetweenBusStopsSoln().DistanceBetweenBusStops(distance, start, destination);

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void DistanceBetweenBusStopsSoln_Second()
        {
            var distance = new int[] { 1, 2, 3, 4 };
            var start = 0;
            var destination = 2;

            var output = 3;

            var res = new DistanceBetweenBusStopsSoln().DistanceBetweenBusStops(distance, start, destination);

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void DistanceBetweenBusStopsSoln_Third()
        {
            var distance = new int[] { 1, 2, 3, 4 };
            var start = 0;
            var destination = 3;

            var output = 4;

            var res = new DistanceBetweenBusStopsSoln().DistanceBetweenBusStops(distance, start, destination);

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void DistanceBetweenBusStopsSoln_Fourt()
        { 
            var distance = new int[] { 7, 10, 1, 12, 11, 14, 5, 0 };
            var start = 7;
            var destination = 2;

            var output = 17;

            var res = new DistanceBetweenBusStopsSoln().DistanceBetweenBusStops(distance, start, destination);

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void DistanceBetweenBusStopsSoln_Fifth()
        {           
            var distance = new int[] { 3, 6, 7, 2, 9, 10, 7, 16, 11 };
            var start = 6;
            var destination = 2;

            var output = 28;

            var res = new DistanceBetweenBusStopsSoln().DistanceBetweenBusStops(distance, start, destination);

            Assert.AreEqual(output, res);
        }

        [TestMethod]
        public void DistanceBetweenBusStopsSoln_Sixth()
        {            
            var distance = new int[] { 14, 13, 4, 7, 10, 17, 8, 3, 2, 13 };
            var start = 2;
            var destination = 9;

            var output = 40;

            var res = new DistanceBetweenBusStopsSoln().DistanceBetweenBusStops(distance, start, destination);

            Assert.AreEqual(output, res);
        }
    }
}