2078. Two Furthest Houses With Different Colors | LeetCode Easy | Python Solution | Array, Greedy

Опубликовано: 24 Декабрь 2022
на канале: Shaheer Shukur

614

Leetcode easy problem 2078. Two Furthest Houses With Different Colors, detailed explanation and solution in python language.

LeetCode Problem Link: https://leetcode.com/problems/two-fur...
Solution (Python Code): https://github.com/shaheershukur/Leet...

#leetcode #python #solution

Problem Statement:
There are n houses evenly lined up on the street, and each house is beautifully painted. You are given a 0-indexed integer array colors of length n, where colors[i] represents the color of the ith house.

Return the maximum distance between two houses with different colors.

The distance between the ith and jth houses is abs(i - j), where abs(x) is the absolute value of x.
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given an array of integers, where each integer represents a color of the house.
we need to find out the maximum distance between two houses with different colors. means, we need to find out the maximum distance between two different numbers in the array.

we know that, logically, the maximum distance between houses can be attained only when 1 house is at the extreme end.
either it can be at the extreme left, or it can be at the extreme right.

lets take few examples to understand this.
here, the maximum distance is between the red house and the blue houses at the extreme ends.

lets take another example.
in this case, this is one possiblity. this yellow house and the black the house at the right extreme has the maximum distance between them.

in this case, this is one possiblity. this green house and the red house at the right extreme has the maximum distance between them.

and in this case, the distance between these two houses is the maximum.

so, based on these observations, we can conclude that, the maximum distance is always between an element in the array and one of the extreme ends of the array.
ie, either the leftmost element or the rightmost element in the array is always a part of the maximum distance.

so, what we can do is, in a single pass, at each element in the array, we will calculate the distance from the leftmost element and from the rightmost element.
and whenever we find a new maximum distance, we will store it.

now, lets code the solution.

we will store the length of the array in this variable.

initially we will set the maximum distance found out to 0.
and at last we will be returning this variable.

now we will go through the entire array once.
during each iteration, for the current element, we will calculate the distance from the leftmost element and the rightmost element.
we need to consider the distance only if the color of the houses are different. else we dont have to calculate the distance, and therefore we can set it to 0.

and we will be updating the variable as we find out a new maximum distance.