738. Monotone Increasing Digits
Problem Link: 738. Monotoen Increasing Digits
Givan a non-negative integer N, find the largest number that is less than or equal to N and whose digits are monotonically increasing. An integer is monotonically increasing if for every adjacent pair of digits, x <= y.
Example 1:
- Input: N = 10
- Output: 9
Approach
Brute Force
We can iterate from N downwards and check if each number satisfies the monotone increasing condition.
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
def is_monotone(num: int) -> bool:
digits = list(str(num))
for i in range(len(digits) - 1):
if digits[i] > digits[i + 1]:
return False
return True
for i in range(N, -1, -1):
if is_monotone(i):
return i
return 0
Greedy
To find largest monotone increasing number ≤ N, consider a two-digit example: 98. If we see a decreasing pair (9 > 8), we reduce the left digit by 1 (9 -> 8) and set all following digits to 9, resulting in 89.
Traversal order: We must traverse from right to left. If we traverse left to right, reducing a digit might break the monotonicity with previous digits. For example, 332: left-to-right gives 329 (still not monotone because 3 > 2), while right-to-left gives 332 -> 329 -> 299 (correct).
The greedy choice is: when we find strNum[i-1] > strNum[i], we decrement strNum[i-1] and mark the position i as the start for setting all subsequent digits to 9.
class Solution:
def monotoneIncreasingDigits(self, N: int) -> int:
digits = list(str(N))
n = len(digits)
mark = n # position from where we set digits to 9
for i in range(n - 1, 0, -1):
if digits[i - 1] > digits[i]:
mark = i
digits[i - 1] = chr(ord(digits[i - 1]) - 1)
for i in range(mark, n):
digits[i] = '9'
return int(''.join(digits))
968. Binary Tree Cameras
Problem Link: 968. Binary Tree Cameras
Given a binary tree, we install cameras on nodes. Each camera can monitor its parent, itself, and its immediate children. Find the minimum number of cameras needed to monitor all nodes.
Approach
Key insight: Placing cameras on leaf nodes is wasteful because a camera covers three levels. The optimal strategy is to place cameras on the parents of leaf nodes, then skip two levels and repeat.
Logic: We process the tree bottom-up (post-order traversal) and assign states to each node:
- 0: Not covered
- 1: Has a camera
- 2: Covered (by a camera elsewhere)
Empty nodes (null) are considered as covered (state 2) so that leaf nodes don't force unnecessary cameras.
Post-order traversal: We visit left child, right child, then the current node. Based on the children's states, we decide the current node's state and whether to place a camera.
State transitions:
- Both children covered (2): Current node is not covered (0). A camera should be placed at its parent.
- Any child is not covered (0): Current node must have a camera (1).
- Any child has a camera (1): Current node is covered (2).
After traversal, check the root: if it is not covered (0), we need an additional camera.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def minCameraCover(self, root: TreeNode) -> int:
self.cameras = 0
def dfs(node: TreeNode) -> int:
# Returns state: 0 = not covered, 1 = has camera, 2 = covered
if not node:
return 2 # null nodes are considered covered
left = dfs(node.left)
right = dfs(node.right)
# If any child is not covered, place a camera here
if left == 0 or right == 0:
self.cameras += 1
return 1
# If any child has a camera, this node is covered
if left == 1 or right == 1:
return 2
# Both children are covered, this node is not covered
return 0
# If root ends up not covered, add one camera
if dfs(root) == 0:
self.cameras += 1
return self.cameras
Summary
Greedy algorithms work when we can find a locally optimal choice that leads to a globally optimal solution. In the monotone digits problem, we greedily fix violations from right to left. In the camera problem, we greedily place cameras at leaf parents. Both approaches avoid brute force and achieve efficient solutions.