1. Problem Statement (Simple Explanation): You’re given an array height of length n: Each height[i] is a non-negative integer representing a bar’s height. The width of each bar is 1. Imagine this array as an elevation map. You must compute how many units of water can be trapped between the bars after raining. 2. Examples: Example 1: Input: height = [0,1,0,2,1,0,1,3,2,1,2,1] Visualization shows 6 units of trapped water. Output: 6 Example 2: Input: height = [4,2,0,3,2,5] Trapped water: Between 4 and 3: 2 units above index 1, 4 units above index 2 (total 6). Between 3 and 5: 1 unit above index 4, 2 units above index 3 (total 3). Total: 6 + 3 = 9. Output: 9 3. Intuition: At any position i, the water height is: water_at_i = min(max_left[i], max_right[i]) - height[i] where: max_left[i] = max height on the left of i including i. max_right[i] = max height on the right of i ...
1. Problem Statement (Simple Explanation): You’re given an unsorted integer array nums. You must return the smallest positive integer (i.e., >= 1) that is not present in nums. Constraints: Must run in O(n) time. Must use O(1) auxiliary space (i.e., in-place; ignoring input array itself). 2. Examples: Example 1: Input: nums = [1,2,0] Present positives: 1, 2. Missing smallest positive: 3 . Output: 3 Example 2: Input: nums = [3,4,-1,1] Present positives: 1, 3, 4. Smallest missing positive is 2 . Output: 2 Example 3: Input: nums = [7,8,9,11,12] No 1 in the array, so the smallest missing positive is 1 . Output: 1 3. Key Insight: For an array of length n: The smallest missing positive integer is always in the range: [1, n+1] Because: In the best case, the array contains all 1..n, so the answer is n+1. Otherwise, some number in 1..n...