This is an interesting problem involving Binary search.
Here is the link to the problem — https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
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. …
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.
rows = 0
col = 0
A = 0
def shortestBridge(self, A: List[List[int]]) -> int:
self.col = len(A)
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
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:
elif 0<=x<self.rows …