Greedy

Given an array of integers `nums`, find the subarray with the largest sum and return the sum. A **subarray** is a contiguous non-empty sequence of elements within an array. **Example 1:** ```java Input: nums = [2,-3,4,-2,2,1,-1,4] Output: 8 ``` Explanation: The subarray [4,-2,2,1,-1,4] has the largest sum 8. **Example 2:** ```java Input: nums = [-1] Output: -1 ``` **Constraints:** * `1 <= nums.length <= 1000` * `-1000 <= nums[i] <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force approach would be to compute the sum of every subarray and return the maximum among them. This would be an <code>O(n^2)</code> approach. Can you think of a better way? Maybe you should consider a dynamic programming-based approach. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Instead of calculating the sum for every subarray, try maintaining a running sum. Maybe you should consider whether extending the previous sum or starting fresh with the current element gives a better result. Can you think of a way to track this efficiently? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We use a variable <code>curSum</code> to track the sum of the elements. At each index, we have two choices: either add the current element to <code>curSum</code> or start a new subarray by resetting <code>curSum</code> to the current element. Maybe you should track the maximum sum at each step and update the global maximum accordingly. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> This algorithm is known as Kadane's algorithm. </p> </details>

You are given an integer array `nums` where each element `nums[i]` indicates your maximum jump length at that position. Return `true` if you can reach the last index starting from index `0`, or `false` otherwise. **Example 1:** ```java Input: nums = [1,2,0,1,0] Output: true ``` Explanation: First jump from index 0 to 1, then from index 1 to 3, and lastly from index 3 to 4. **Example 2:** ```java Input: nums = [1,2,1,0,1] Output: false ``` **Constraints:** * `1 <= nums.length <= 1000` * `0 <= nums[i] <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force approach would be to recursively explore all paths from index <code>0</code> to its reachable indices, then process those indices similarly, returning <code>true</code> if we reach the last index. This would be an exponential approach. Can you think of a better way? Maybe a greedy approach works. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Instead of processing the array from index <code>0</code>, start from the last index. Let the target index be <code>goal = n - 1</code>. Iterate in reverse from index <code>n - 2</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> At each iteration, we check whether the current index can reach <code>goal</code>. If it can, we update <code>goal</code> to the current index, as reaching the current index means we can also reach the <code>goal</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> To determine if we can reach the last index, the <code>goal</code> should be <code>0</code> after the iteration. Otherwise, reaching the last index is not possible. </p> </details>

You are given an array of integers `nums`, where `nums[i]` represents the maximum length of a jump towards the right from index `i`. For example, if you are at `nums[i]`, you can jump to any index `i + j` where: * `j <= nums[i]` * `i + j < nums.length` You are initially positioned at `nums[0]`. Return the minimum number of jumps to reach the last position in the array (index `nums.length - 1`). You may assume there is always a valid answer. **Example 1:** ```java Input: nums = [2,4,1,1,1,1] Output: 2 ``` Explanation: Jump from index `0` to index `1`, then jump from index `1` to the last index. **Example 2:** ```java Input: nums = [2,1,2,1,0] Output: 2 ``` **Constraints:** * `1 <= nums.length <= 1000` * `0 <= nums[i] <= 100` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force approach would be to recursively explore all paths from index <code>0</code> to its reachable indices, then process those indices similarly and return the minimum steps to reach the last index. This would be an exponential approach. Can you think of a better way? Maybe a greedy approach works. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We maintain two pointers, <code>l</code> and <code>r</code>, initially set to <code>0</code>, representing the range of reachable indices. At each step, we iterate through the indices in the range <code>l</code> to <code>r</code> and determine the farthest index that can be reached from the current range. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We then update the pointers <code>l</code> and <code>r</code> to the next range, setting <code>l</code> to <code>r + 1</code> and <code>r</code> to the farthest index reachable from the current range. We continue this process until the pointers go out of bounds. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> The number of steps taken represents the minimum steps required to reach the last index, as it is guaranteed that we can reach it. </p> </details>

There are `n` gas stations along a circular route. You are given two integer arrays `gas` and `cost` where: * `gas[i]` is the amount of gas at the `ith` station. * `cost[i]` is the amount of gas needed to travel from the `ith` station to the `(i + 1)th` station. (The last station is connected to the first station) You have a car that can store an unlimited amount of gas, but you begin the journey with an empty tank at one of the gas stations. Return the starting gas station's index such that you can travel around the circuit once in the clockwise direction. If it's impossible, then return `-1`. It's guaranteed that at most one solution exists. **Example 1:** ```java Input: gas = [1,2,3,4], cost = [2,2,4,1] Output: 3 ``` Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 0. Your tank = 4 - 1 + 1 = 4 Travel to station 1. Your tank = 4 - 2 + 2 = 4 Travel to station 2. Your tank = 4 - 2 + 3 = 5 Travel to station 3. Your tank = 5 - 4 + 4 = 5 **Example 2:** ```java Input: gas = [1,2,3], cost = [2,3,2] Output: -1 ``` Explanation: You can't start at station 0 or 1, since there isn't enough gas to travel to the next station. If you start at station 2, you can move to station 0, and then station 1. At station 1 your tank = 0 + 3 - 2 + 1 - 2 = 0. You're stuck at station 1, so you can't travel around the circuit. **Constraints:** * `1 <= gas.length == cost.length <= 1000` * `0 <= gas[i], cost[i] <= 1000` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force approach would be to start at each gas station, simulate the process, and return the index where completing the circuit is possible. This would be an <code>O(n^2)</code> time solution. Can you think of a better way? Maybe a greedy approach works. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can immediately return <code>-1</code> if <code>sum(gas) < sum(cost)</code>, as completing the circuit is impossible due to insufficient gas. Otherwise, a solution always exists because the total gas is sufficient to cover the total cost, meaning there must be a valid starting point that allows completing the circuit. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We start with a variable <code>total</code> to track the gas balance and initialize the result index to <code>0</code>. As we iterate through the array with index <code>i</code>, we accumulate the difference <code>(gas[i] - cost[i])</code>. If <code>total</code> becomes negative at any index, we reset it to <code>0</code> and update the result index to <code>(i + 1)</code>. </p> </details>

You are given an integer array `hand` where `hand[i]` is the value written on the `ith` card and an integer `groupSize`. You want to rearrange the cards into groups so that each group is of size `groupSize`, and card values are consecutively increasing by `1`. Return `true` if it's possible to rearrange the cards in this way, otherwise, return `false`. **Example 1:** ```java Input: hand = [1,2,4,2,3,5,3,4], groupSize = 4 Output: true ``` Explanation: The cards can be rearranged as `[1,2,3,4]` and `[2,3,4,5]`. **Example 2:** ```java Input: hand = [1,2,3,3,4,5,6,7], groupSize = 4 Output: false ``` Explanation: The closest we can get is `[1,2,3,4]` and `[3,5,6,7]`, but the cards in the second group are not consecutive. **Constraints:** * `1 <= hand.length <= 1000` * `0 <= hand[i] <= 1000` * `1 <= groupSize <= hand.length` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(nlogn)</code> time and <code>O(n)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> It is observed that to form a group, the minimum value should be the starting value of the group. Additionally, the minimum value in the array serves as the starting value for one or more groups based on its frequency. Can you think of an efficient way to determine the frequencies of array elements? Maybe a specific data structure can be useful here. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can use a hash map to store the elements along with their frequencies. Additionally, we sort the given array. Then, we iterate through the sorted array and try to form groups by decrementing the frequency count. If we fail to form a group at any step, we immediately return <code>false</code>. Can you think why this works? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Sorting ensures we start with the smallest available value, while the hash map helps track element availability using frequency counts. At each step, we pick the smallest available value <code>x</code> and attempt to form a group from <code>x</code> to <code>x + groupSize - 1</code>. If all elements are present based on their frequency counts, we decrement their counts as we iterate. If we successfully form all groups, we return <code>true</code>; otherwise, we return <code>false</code>. </p> </details>

You are given a 2D array of integers `triplets`, where `triplets[i] = [ai, bi, ci]` represents the `ith` **triplet**. You are also given an array of integers `target = [x, y, z]` which is the triplet we want to obtain. To obtain `target`, you may apply the following operation on `triplets` zero or more times: Choose two **different** triplets `triplets[i]` and `triplets[j]` and update `triplets[j]` to become `[max(ai, aj), max(bi, bj), max(ci, cj)]`. * E.g. if `triplets[i] = [1, 3, 1]` and `triplets[j] = [2, 1, 2]`, `triplets[j]` will be updated to `[max(1, 2), max(3, 1), max(1, 2)] = [2, 3, 2]`. Return `true` if it is possible to obtain `target` as an **element** of `triplets`, or `false` otherwise. **Example 1:** ```java Input: triplets = [[1,2,3],[7,1,1]], target = [7,2,3] Output: true ``` Explanation: Choose the first and second triplets, update the second triplet to be [max(1, 7), max(2, 1), max(3, 1)] = [7, 2, 3]. **Example 2:** ```java Input: triplets = [[2,5,6],[1,4,4],[5,7,5]], target = [5,4,6] Output: false ``` **Constraints:** * `1 <= triplets.length <= 1000` * `1 <= ai, bi, ci, x, y, z <= 100` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(1)</code> space, where <code>n</code> is the size of the input array. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> An important observation is that we can ignore triplets with values greater than the target triplet. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> Specifically, if a triplet <code>t</code> has any element greater than the corresponding value in <code>target</code> (i.e., <code>t[0] > target[0]</code>, <code>t[1] > target[1]</code>, or <code>t[2] > target[2]</code>), we can discard it. This is because using such a triplet in operations would exceed the target values, making it invalid. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> Now, from the remaining valid triplets, we only need to check whether the target triplet values exist. Since all values in the valid triplets are less than or equal to the corresponding values in the target triplet, finding the target triplet among them guarantees that we can achieve it. </p> </details>

You are given a string `s` consisting of lowercase english letters. We want to split the string into as many substrings as possible, while ensuring that each letter appears in at most one substring. Return a list of integers representing the size of these substrings in the order they appear in the string. **Example 1:** ```java Input: s = "xyxxyzbzbbisl" Output: [5, 5, 1, 1, 1] ``` Explanation: The string can be split into `["xyxxy", "zbzbb", "i", "s", "l"]`. **Example 2:** ```java Input: s = "abcabc" Output: [6] ``` **Constraints:** * `1 <= s.length <= 100` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution with <code>O(n)</code> time and <code>O(m)</code> space, where <code>n</code> is the length of the string <code>s</code> and <code>m</code> is the number of unique characters in the string <code>s</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A character has a first and last index in the given string. Can you think of a greedy approach to solve this problem? Maybe you should try iterating over one of these two indices. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We store the last index of each character in a hash map or an array. As we iterate through the string, treating each index as a potential start of a partition, we track the end of the partition using the maximum last index of the characters seen so far in the current partition. Additionally, we maintain the size of the current partition using a variable, say <code>size</code>. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> We update the end of the current partition based on the maximum last index of the characters, extending the partition as needed. When the current index reaches the partition’s end, we finalize the partition, append its size to the output list, reset the size to <code>0</code>, and continue the same process for the remaining string. </p> </details>

You are given a string `s` which contains only three types of characters: `'('`, `')'` and `'*'`. Return `true` if `s` is **valid**, otherwise return `false`. A string is valid if it follows all of the following rules: * Every left parenthesis `'('` must have a corresponding right parenthesis `')'`. * Every right parenthesis `')'` must have a corresponding left parenthesis `'('`. * Left parenthesis `'('` must go before the corresponding right parenthesis `')'`. * A `'*'` could be treated as a right parenthesis `')'` character or a left parenthesis `'('` character, or as an empty string `""`. **Example 1:** ```java Input: s = "((**)" Output: true ``` Explanation: One of the `'*'` could be a `')'` and the other could be an empty string. **Example 2:** ```java Input: s = "(((*)" Output: false ``` Explanation: The string is not valid because there is an extra `'('` at the beginning, regardless of the extra `'*'`. **Constraints:** * `1 <= s.length <= 100` <br> <br> <details class="hint-accordion"> <summary>Recommended Time & Space Complexity</summary> <p> You should aim for a solution as good or better than <code>O(n)</code> time and <code>O(n)</code> space, where <code>n</code> is the length of the input string. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 1</summary> <p> A brute force approach would try all possibilities when encountering a <code>'*'</code> and recursively solve the problem, leading to an exponential approach. Can you think of a better way? Maybe a data structure commonly used in parenthesis problems could be useful. </p> </details> <br> <details class="hint-accordion"> <summary>Hint 2</summary> <p> We can solve the problem using a stack-based approach. We maintain two stacks: one for tracking the indices of left parentheses and another for star indices. As we iterate through the string from left to right, we push indices onto their respective stacks when encountering a left parenthesis <code>'('</code> or a star <code>'*'</code>. Can you determine the logic for the right parentesis case? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 3</summary> <p> If the left parenthesis stack is not empty, we pop from it. Otherwise, we pop from the star stack, treating the star as a left parenthesis to keep the string valid. After iterating the string, the stacks might be non-empty? Can you determine the logic for this case? </p> </details> <br> <details class="hint-accordion"> <summary>Hint 4</summary> <p> Now, we try to match the remaining left parentheses with stars, ensuring the stars appear after the left parentheses in the string. We simultaneously pop from both stacks, and if the index of a left parenthesis is greater than that of a star, the string is invalid as there is no matching right parenthesis. In this case, we return <code>false</code>. </p> </details>