This is an interesting problem involving Binary search.
Here is the link to the problem —

class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
gLow, gHigh = 0, 0
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high)//2
#print(low, high, mid)
if target < nums[mid]:
high = mid - 1
low = mid + 1
gHigh = high
# re-initialized for finding low. …

Union Find is a very interesting data-structure that makes a lot of graph problems easy to solve.

Let’s say, you have a set of N elements that are partitioned into further subsets, and you have to keep track of connectivity of each element in a particular subset or connectivity of subsets with each other. To do this operation efficiently, you can use the Union-Find Data Structure.

There is a naive version of this which can be done in O(N²) time complexity and O(N) space complexity. However, I am excited to jump into the cooler version, and we are going to more optimizations to reduce the union-find to O(log *N) time complexity. …

Here is one of the solutions I understood, I am putting it here for future reference. I have added comments to make it easier to understand.

# Start with picking the first 1 you can find. 
# Pick that point and start dfs to all all the edges for that island.
# Now start bfs on the elements and exit when we find the second island, and quit when next 1 is found.
class Solution:
rows = 0
col = 0
A = 0
def shortestBridge(self, A: List[List[int]]) -> int:
self.col = len(A[0])
self.rows = len(A)
self.A = A
bfs = []
self.dfs(bfs, *self.first(self.rows, self.col))

# Final bfs logic to start expanding from each of the nodes of the first island.
count = 0
while bfs:
newBfsStack = []
for i,j in bfs:
for x,y in ((i-1, j),(i+1, j),(i, j-1),(i, j+1)):
if 0<=x<self.rows and 0<=y<self.col and self.A[x][y] == 1:
return count
elif 0<=x<self.rows …

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store