June 30, 2018
Hey Developer,
I am bringing you another high quality Java solution. This time, I am solving the Passing Cars problem which can be found here.
My solution has runtime of O(N). The key to solving this problem in O(N) time is 1 simple observation about our array.
Explanation:
If we look at the array below we can see that any time we have a 0 to the left of a 1 that counts as a passing car. That’s the whole problem! The code is fairly simple.
Every time we get a 0, we increment carsTravelingEast. Every time we encounter a 1 or a car traveling west, we increment passingCars by the number of carsTravelingEast.
Below is the code for my Java solution.
class Solution { public int solution(int[] A) { // limit on number of passing cars (given in problem description) (1,000,000,000) final int CAR_LIMIT = 1000000000; // counter for number of passing cars int passingCars = 0; // number of zeroes OR cars traveling east int carsTravelingEast = 0; // number of elements in A int N = A.length; // iterate through A for (int i = 0; i < N; i++) { // increment number of cars traveling east if (A[i] == 0) { carsTravelingEast++; } //If you have at least 1 car traveling East and you encounter a car traveling west if (A[i] == 1 && carsTravelingEast > 0) { passingCars += carsTravelingEast; // if passing cars exceeds limit set by problem description if (passingCars > CAR_LIMIT) return -1; } } return passingCars; } }