In this post I'll walk through my solutions to all four questions in the weekly leetcode contest from July 5th, 2025.
Question 1: Coupon Code Validator
You are given three arrays of length n that describe the properties of n coupons: code, businessLine, and isActive.
The ith coupon has:
code[i]: a string representing the coupon identifier.businessLine[i]: a string denoting the business category of the coupon.isActive[i]: a boolean indicating whether the coupon is currently active.
A coupon is considered valid if all of the following conditions hold:
code[i]is non-empty and consists only of alphanumeric characters (a-z, A-Z, 0-9) and underscores (_).businessLine[i]is one of the following four categories:"electronics","grocery","pharmacy","restaurant".isActive[i]is true.
Return an array of the codes of all valid coupons, sorted first by their businessLine in the order: "electronics", "grocery", "pharmacy", "restaurant", and then by code in lexicographical (ascending) order within each category.
Solution
In terms of algorithms and data structures, this is a very simple problem, but implementing it quickly in a competitive programming contest is a bit annoying. You just need to validate the coupon codes, make sure they're active, and sort them by the business line.
Python Code
def validCode(self, c):
if not c:
return False
for ch in c:
if not ch.isalnum() and ch != '_':
return False
return True
def validateCoupons(self, code: List[str], businessLine: List[str], isActive: List[bool]) -> List[str]:
answer = []
e = []
g = []
p = []
r = []
n = len(code)
for i in range(n):
c = code[i]
l = businessLine[i]
active = isActive[i]
if l not in ["electronics", "grocery", "pharmacy", "restaurant"]:
continue
if not active:
continue
if not self.validCode(c):
continue
if l == "electronics":
e.append(c)
elif l == "grocery":
g.append(c)
elif l == "pharmacy":
p.append(c)
else:
r.append(c)
e.sort()
g.sort()
p.sort()
r.sort()
return e + g + p + r
Question 2: Power Grid Maintenance
You are given an integer c representing c power stations, each with a unique identifier id from 1 to c (1‑based indexing).
These stations are interconnected via n bidirectional cables, represented by a 2D array connections, where each element connections[i] = [ui, vi] indicates a connection between station ui and station vi. Stations that are directly or indirectly connected form a power grid.
Initially, all stations are online (operational).
You are also given a 2D array queries, where each query is one of the following two types:
[1, x]: A maintenance check is requested for stationx. If stationxis online, it resolves the check by itself. If stationxis offline, the check is resolved by the operational station with the smallestidin the same power grid asx. If no operational station exists in that grid, return -1.[2, x]: Stationxgoes offline (i.e., it becomes non-operational).
Return an array of integers representing the results of each query of type [1, x] in the order they appear.
Solution
We can use Union-Find to find the connected components in the graph. Use this union-find to get all powerstations in each component, and form a MinHeap for each connected component. Then just keep track of which stations are offline, and we have everything we need to answer the queries.
Python Code
import heapq
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, i):
if self.parent[i] == i:
return i
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
root_i = self.find(i)
root_j = self.find(j)
if root_i != root_j:
if self.rank[root_i] < self.rank[root_j]:
self.parent[root_i] = root_j
elif self.rank[root_j] < self.rank[root_i]:
self.parent[root_j] = root_i
else:
self.parent[root_j] = root_i
self.rank[root_i] += 1
return True
return False
class Solution:
def processQueries(self, c: int, connections: List[List[int]], queries: List[List[int]]) -> List[int]:
n = len(connections)
uf = UnionFind(c+1)
for i in range(n):
u, v = connections[i]
uf.union(u, v)
mapp = {}
for i in range(1, c+1):
parent = uf.find(i)
if parent in mapp:
mapp[parent].append(i)
else:
mapp[parent] = [i]
for k, v in mapp.items():
heapq.heapify(v)
offline = {}
answer = []
for q in queries:
code, x = q
if code == 1:
if x not in offline:
answer.append(x)
continue
else:
v = mapp[uf.find(x)]
if not v:
answer.append(-1)
continue
myMin = v[0]
a = None
while myMin in offline:
heapq.heappop(v)
if not v:
a = -1
break
myMin = v[0]
if myMin not in offline:
a = myMin
answer.append(a)
if code == 2:
offline[x] = True
return answer
Question 3: Minimum Time for K Connected Components
You are given an integer n and an undirected graph with n nodes labeled from 0 to n - 1. This is represented by a 2D array edges, where edges[i] = [ui, vi, timei] indicates an undirected edge between nodes ui and vi that can be removed at timei.
You are also given an integer k.
Initially, the graph may be connected or disconnected. Your task is to find the minimum time t such that after removing all edges with time <= t, the graph contains at least k connected components.
Return the minimum time t.
Solution
Again, we want to find the connected components in the graph, so we can use Union-Find. In this question, we want to find the minimum time t such that there are k connected components in the graph. The constraints are pretty loose here, so we can just binary search over all possible time-values, remove all expired edges at our guessed time, and use union-find to get the connected components.
Python Code
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, i):
if self.parent[i] == i:
return i
self.parent[i] = self.find(self.parent[i])
return self.parent[i]
def union(self, i, j):
root_i = self.find(i)
root_j = self.find(j)
if root_i != root_j:
if self.rank[root_i] < self.rank[root_j]:
self.parent[root_i] = root_j
elif self.rank[root_j] < self.rank[root_i]:
self.parent[root_j] = root_i
else:
self.parent[root_j] = root_i
self.rank[root_i] += 1
return True
return False
class Solution:
def findComponents(self, n, edges, t, k):
uf = UnionFind(n)
for u, v, t1 in edges:
if t1 > t:
uf.union(u, v)
unique = 0
seen = {}
for i in range(n):
p = uf.find(i)
if p in seen:
continue
else:
unique += 1
seen[p] = True
return unique >= k
def minTime(self, n: int, edges: List[List[int]], k: int) -> int:
times = [0]
for u, v, t in edges:
times.append(t)
times = list(set(times))
times.sort()
low = 0
high = len(times)
best = None
while low < high:
guess = (low + high) // 2
t = times[guess]
if self.findComponents(n, edges, t, k):
if best is None:
best = t
else:
best = min(best, t)
high = guess
continue
else:
low = guess + 1
continue
if best is not None:
return best
else:
return -1
Question 4: Minimum Moves to Reach Target in Grid
You are given four integers sx, sy, tx, and ty, representing two points (sx, sy) and (tx, ty) on an infinitely large 2D grid.
You start at (sx, sy).
At any point (x, y), define m = max(x, y). You can either:
- Move to
(x + m, y), or - Move to
(x, y + m).
Return the minimum number of moves required to reach (tx, ty). If it is impossible to reach the target, return -1.
Solution
The first, most obvious attempt is to use BFS from the starting (sx, sy) tuple. This is probably exponential, and quickly runs into the memory limit on leetcode.
After failing to optimize the first solution, we can try starting over and working backwards from (tx, ty) and trying to find (sx, sy) in the minimum number of moves.
In fact, if you think about the moves in reverse, there is only one possible previous point (px, py) for almost every point (x,y). For simplicity, let's assume x > y:
x > 2*y: In this case,px > py, so the previous point must be(x/2, y). If x is odd, we have reached an impossible statex < 2*y: In this case,py > px, so thenx = px + py. Therefore, the previous point was(x-y, y).x = y: In this case, we can either come from(x, 0), or(0, y). It should be obvious based on(sx, sy)which path to choose.
Python Code
class Solution:
def oneTurn(self, x, y):
if x > y:
h = x // 2
if x % 2 == 0 and h >= y:
return (h, y)
if h > y and x % 2 == 1:
return (-1, -1)
if h < y:
return (x-y, y)
elif y > x:
h = y // 2
if y % 2 == 0 and h >= x:
return (x, h)
if h > x and y % 2 == 1:
return (-1, -1)
if h < x:
return (x, y-x)
return (-1, -1)
def minMoves(self, sx: int, sy: int, tx: int, ty: int) -> int:
x = tx
y = ty
moves = 0
while True:
if x == sx and y == sy:
return moves
if x < sx or y < sy:
return -1
if x == y:
temp1 = self.minMoves(sx, sy, 0, y)
temp2 = self.minMoves(sx, sy, x, 0)
temps = []
if temp1 != -1:
temps.append(temp1)
if temp2 != -1:
temps.append(temp2)
if not temps:
return -1
return moves + min(temps) + 1
t = self.oneTurn(x, y)
if t == (-1, -1):
return -1
x = t[0]
y = t[1]
moves += 1
return -1