Problem Requirement Design a stack named MinStack that supports these operations: MinStack(): initialize the stack. push(value): push value onto the stack. pop(): remove the top element. top(): return the top element. getMin(): return the minimum element in the stack. Every operation must run in O(1) time. pop, top, and getMin are called only when the stack is non-empty, so no additional empty-stack return value is needed. Example Operations: ["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"] Arguments: [[], [-2], [0], [-3], [], [], [], []] Output: [null, null, null, null, -3, null, 0, -2] The sequence corresponds to: ...
LeetCode 20: Valid Parentheses, Why Equal Counts Are Not Enough
Problem Requirement You are given a string s containing only these six characters: ( ) { } [ ] Determine whether the string is valid. A valid string must satisfy all three conditions: Every opening bracket is closed by the same type of closing bracket. Opening brackets are closed in the correct order. Every closing bracket has a corresponding opening bracket of the same type. Return True when all conditions hold; otherwise, return False. ...
LeetCode 394: Decode String by Saving and Restoring Nested Context
Problem Requirement Given an encoded string s, return its decoded string. The encoding rule is: k[encoded_string] The encoded_string inside the brackets is repeated exactly k times, where k is a positive integer. Encodings may be nested or adjacent to ordinary lowercase letters. The problem guarantees that: The input is always valid, with matching brackets and no extra spaces. Original text contains no digits; digits only represent repeat counts. Inputs such as 3a or 2[4] do not occur. The decoded string length does not exceed 10^5. Examples Input Output "3[a]2[bc]" "aaabcbc" "3[a2[c]]" "accaccacc" "2[abc]3[cd]ef" "abcabccdcdcdef" Constraints 1 <= s.length <= 30 s contains only lowercase English letters, digits, and [] Every repeat count is in [1, 300] LeetCode provides this method signature: ...
LeetCode 74: Search a 2D Matrix
You are given an m x n integer matrix matrix and an integer target. Return True if target is in the matrix; otherwise, return False. The matrix satisfies two conditions: Every row is sorted in non-decreasing order. The first integer of each row is strictly greater than the last integer of the previous row. The required time complexity is O(log(m * n)). For example, consider this matrix: 1 3 5 7 10 11 16 20 23 30 34 60 When target = 3, return True. When target = 13, return False. The constraints are: ...
LeetCode 153: Find Minimum in Rotated Sorted Array
Problem Requirement The input is a non-empty integer array nums. Every element is unique, and before rotation the array was sorted in strictly increasing order. The array is rotated between 1 and nums.length times. One rotation moves the last element to the front; therefore, nums.length rotations restore the original increasing order. Return the minimum value in the rotated array. The problem requires an algorithm with O(log n) runtime. LeetCode uses this method contract: ...
LeetCode 33: Search in Rotated Sorted Array
Problem Requirement The input gives an integer array nums and an integer target. Every value in nums is distinct, and the array was strictly increasing before rotation. Before the method is called, it may be rotated at an unknown index k (0 <= k < nums.length) into: [nums[k], ..., nums[n-1], nums[0], ..., nums[k-1]] Return the index of target in the rotated array when it exists; otherwise return -1. The problem requires an algorithm with O(log n) runtime. ...
LeetCode 503: Where Does the Right Side End in a Circular Array?
Problem Requirement You are given a circular integer array nums. Return an array answer. For every index i: answer[i] = the first value strictly greater than nums[i] when moving right If one full trip around the array finds no greater value, answer[i] = -1. “Circular” means that moving past the final position continues from index 0. An index cannot travel one full circle and use itself as its own answer. ...
LeetCode 84: Which Bar Limits a Contiguous Rectangle?
Problem Requirement You are given a non-negative integer array heights. Each heights[i] is the height of a bar with width 1, and all bars are adjacent. Return the area of the largest rectangle that can be formed in the histogram. A legal rectangle covers a contiguous interval of bars. Its width is the number of bars in that interval, and its height cannot exceed the shortest bar in the interval. ...
LeetCode 136: Single Number Without Growing Extra Storage
Problem Requirement You are given a non-empty integer array nums. Exactly one element appears once. Every other element appears exactly twice. Return the element that appears once. LeetCode provides this method contract: singleNumber(nums: List[int]) -> int The solution must also satisfy two resource requirements: O(n) time O(1) extra space Example 1 Input: nums = [2,2,1] Output: 1 2 appears twice. Only 1 appears once. Example 2 Input: nums = [4,1,2,1,2] Output: 4 Both 1 and 2 have matching copies. Only 4 remains unpaired. ...
LeetCode 191: Number of 1 Bits and How to Skip Irrelevant Zeros
Problem Requirement Given a positive integer n, return the number of 1 bits in its binary representation. This count is also called the Hamming weight. LeetCode provides this method contract: hammingWeight(n: int) -> int Example 1 Input: n = 11 Binary: 1011 Output: 3 Example 2 Input: n = 128 Binary: 10000000 Output: 1 Constraints 1 <= n <= 2^31 - 1 The input stays in the problem’s non-negative integer domain. Although the current constraints start at 1, the implementation also handles n = 0 naturally and returns 0. ...