Greedy

Given an integer array nums, find the subarray with the largest sum, and return _its sum_. Example 1: Input: nums = \[-2,1,-3,4,-1,2,1,-5,4\] Output: 6 Explanation: The subarray \[4,-1,2,1\] has the largest sum 6. Example 2: Input: nums = \[1\] Output: 1 Explanation: The subarray \[1\] has the largest sum 1. Example 3: Input: nums = \[5,4,-1,7,8\] Output: 23 Explanation: The subarray \[5,4,-1,7,8\] has the largest sum 23. Constraints: * `1...

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. Example 1: Input: grid = \[\[1,3,1\],\[1,5,1\],\[4,2,1\]\] Output: 7 Explanation: Because the path 1 -> 3 -> 1 -> 1 -> 1 minimizes the sum. Example 2: Input: grid = \[\[1,2,3\],\[4,5,6\]\] Output: 12 Constraints: * m == grid.length * `n ...

We are playing the Guessing Game. The game will work as follows: 1. I pick a number between 1 and n. 2. You guess a number. 3. If you guess the right number, you win the game. 4. If you guess the wrong number, then I will tell you whether the number I picked is higher or lower, and you will continue guessing. 5. Every time you guess a wrong number x, you will pay x dollars. If you run out of money, you lose the game. Given a particular n, return _the minimum amount of mo...

Given a positive integer n, you can apply one of the following operations: 1. If n is even, replace n with n / 2. 2. If n is odd, replace n with either n + 1 or n - 1. Return _the minimum number of operations needed for_ n _to become_ 1. Example 1: Input: n = 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1 Example 2: Input: n = 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1 Example 3: Input: n = 4 Output: 2 **C...

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number. Example 1: **I...

There are buckets buckets of liquid, where exactly one of the buckets is poisonous. To figure out which one is poisonous, you feed some number of (poor) pigs the liquid to see whether they will die or not. Unfortunately, you only have minutesToTest minutes to determine which bucket is poisonous. You can feed the pigs according to these steps: 1. Choose some live pigs to feed. 2. For each pig, choose which buckets to feed it. The pig will consume all the chosen buckets simultaneously a...

Imagine you have a special keyboard with the following keys: * A: Print one 'A' on the screen. * Ctrl-A: Select the whole screen. * Ctrl-C: Copy selection to buffer. * Ctrl-V: Print buffer on screen appending it after what has already been printed. Given an integer n, return _the maximum number of_ 'A' _you can print on the screen with at most_ n _presses on the keys_. Example 1: Input: n = 3 Output: 3 Explanation: We can at most get 3 A's on screen by pressing the f...

You are given an integer num. You can swap two digits at most once to get the maximum valued number. Return _the maximum valued number you can get_. Example 1: Input: num = 2736 Output: 7236 Explanation: Swap the number 2 and the number 7. Example 2: Input: num = 9973 Output: 9973 Explanation: No swap. Constraints: * 0 <= num <= 108

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a double booking. A double booking happens when two events have some non-empty intersection (i.e., some moment is common to both events.). The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end. Implement the MyCalendar class: * `My...

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking. A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.). The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end. Implement the `MyCalendarTwo...

You are given an n x n grid representing a field of cherries, each cell is one of three possible integers. * 0 means the cell is empty, so you can pass through, * 1 means the cell contains a cherry that you can pick up and pass through, or * -1 means the cell contains a thorn that blocks your way. Return _the maximum number of cherries you can collect by following the rules below_: * Starting at the position (0, 0) and reaching (n - 1, n - 1) by moving right or down through vali...

You are standing at position 0 on an infinite number line. There is a destination at position target. You can make some number of moves numMoves so that: * On each move, you can either go left or right. * During the ith move (starting from i == 1 to i == numMoves), you take i steps in the chosen direction. Given the integer target, return _the minimum number of moves required (i.e., the minimum_ numMoves_) to reach the destination_. Example 1: Input: target = 2 *...

You are given k identical eggs and you have access to a building with n floors labeled from 1 to n. You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break. Each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you may **reuse*...

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock's price for the current day. The span of the stock's price in one day is the maximum number of consecutive days (starting from that day and going backward) for which the stock price was less than or equal to the price of that day. * For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 becau...

There is a broken calculator that has the integer startValue on its display initially. In one operation, you can: * multiply the number on display by 2, or * subtract 1 from the number on display. Given two integers startValue and target, return _the minimum number of operations needed to display_ target _on the calculator_. Example 1: Input: startValue = 2, target = 3 Output: 2 Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}. **Example...

In a row of dominoes, tops[i] and bottoms[i] represent the top and bottom halves of the ith domino. (A domino is a tile with two numbers from 1 to 6 - one on each half of the tile.) We may rotate the ith domino, so that tops[i] and bottoms[i] swap values. Return the minimum number of rotations so that all the values in tops are the same, or all the values in bottoms are the same. If it cannot be done, return -1. Example 1: Input: tops = \[2,1,2,4,2,2\], bottoms = \[5...

You are given an m x n binary matrix matrix. You can choose any number of columns in the matrix and flip every cell in that column (i.e., Change the value of the cell from 0 to 1 or vice versa). Return _the maximum number of rows that have all values equal after some number of flips_. Example 1: Input: matrix = \[\[0,1\],\[1,1\]\] Output: 1 Explanation: After flipping no values, 1 row has all values equal. Example 2: Input: matrix = \[\[0,1\],\[1,0\]\] **Output...

We are given hours, a list of the number of hours worked per day for a given employee. A day is considered to be a _tiring day_ if and only if the number of hours worked is (strictly) greater than 8. A _well-performing interval_ is an interval of days for which the number of tiring days is strictly larger than the number of non-tiring days. Return the length of the longest well-performing interval. Example 1: Input: hours = \[9,9,6,0,6,6,9\] Output: 3 Explanation: The long...

Alice and Bob continue their games with piles of stones. There are a number of piles arranged in a row, and each pile has a positive integer number of stones piles[i]. The objective of the game is to end with the most stones. Alice and Bob take turns, with Alice starting first. Initially, M = 1. On each player's turn, that player can take all the stones in the first X remaining piles, where 1 <= X <= 2M. Then, we set M = max(M, X). The game continues until all the stones...

Consider a matrix M with dimensions width * height, such that every cell has value 0 or 1, and any square sub-matrix of M of size sideLength * sideLength has at most maxOnes ones. Return the maximum possible number of ones that the matrix M can have. Example 1: Input: width = 3, height = 3, sideLength = 2, maxOnes = 1 Output: 4 Explanation: In a 3\*3 matrix, no 2\*2 sub-matrix can have more than 1 one. The best solution that has 4 ones is: \[1,0,1\] \[0,0,0...

Given a rectangle of size n x m, return _the minimum number of integer-sided squares that tile the rectangle_. Example 1: Input: n = 2, m = 3 Output: 3 Explanation: 3 squares are necessary to cover the rectangle. 2 (squares of 1x1) 1 (square of 2x2) Example 2: Input: n = 5, m = 8 Output: 5 Example 3: Input: n = 11, m = 13 Output: 6 Constraints: * 1 <= n, m <= 13

Given 3 positives numbers a, b and c. Return the minimum flips required in some bits of a and b to make ( a OR b == c ). (bitwise OR operation). Flip operation consists of change any single bit 1 to 0 or change the bit 0 to 1 in their binary representation. Example 1: Input: a = 2, b = 6, c = 5 Output: 3 Explanation: After flips a = 1 , b = 4 , c = 5 such that (a OR b == c) Example 2: Input: a = 4, b = 2, c = 7 Output: 1 Example 3: **I...

You are given a positive integer num consisting only of digits 6 and 9. Return _the maximum number you can get by changing at most one digit (_6 _becomes_ 9_, and_ 9 _becomes_ 6_)_. Example 1: Input: num = 9669 Output: 9969 Explanation: Changing the first digit results in 6669. Changing the second digit results in 9969. Changing the third digit results in 9699. Changing the fourth digit results in 9666. The maximum number is 9969. Example 2: Input: nu...

Given an integer k, _return the minimum number of Fibonacci numbers whose sum is equal to_ k. The same Fibonacci number can be used multiple times. The Fibonacci numbers are defined as: * F1 = 1 * F2 = 1 * Fn = Fn-1 + Fn-2 for n > 2. It is guaranteed that for the given constraints we can always find such Fibonacci numbers that sum up to k. Example 1: Input: k = 7 Output: 2 Explanation: The Fibonacci numbers are: 1, 1, 2, 3, 5, 8, 13, ... For k = 7 we can use 2 + ...

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell. You have two robots that can collect cherries for you: * Robot #1 is located at the top-left corner (0, 0), and * Robot #2 is located at the top-right corner (0, cols - 1). Return _the maximum number of cherries collection using both robots by following the rules below_: * From a cell (i, j), robots...

There are numBottles water bottles that are initially full of water. You can exchange numExchange empty water bottles from the market with one full water bottle. The operation of drinking a full water bottle turns it into an empty bottle. Given the two integers numBottles and numExchange, return _the maximum number of water bottles you can drink_. Example 1: Input: numBottles = 9, numExchange = 3 Output: 13 Explanation: You can exchange 3 empty bottles to get 1 ful...

There are n oranges in the kitchen and you decided to eat some of these oranges every day as follows: * Eat one orange. * If the number of remaining oranges n is divisible by 2 then you can eat n / 2 oranges. * If the number of remaining oranges n is divisible by 3 then you can eat 2 * (n / 3) oranges. You can only choose one of the actions per day. Given the integer n, return _the minimum number of days to eat_ n _oranges_. Example 1: Input: n = 10 Output: 4 **E...

You are given an m x n binary grid grid where 1 represents land and 0 represents water. An island is a maximal 4-directionally (horizontal or vertical) connected group of 1's. The grid is said to be connected if we have exactly one island, otherwise is said disconnected. In one day, we are allowed to change any single land cell (1) into a water cell (0). Return _the minimum number of days to disconnect the grid_. Example 1: Input: grid = \[\[0,1,1...

Given an integer n, you must transform it into 0 using the following operations any number of times: * Change the rightmost (0th) bit in the binary representation of n. * Change the ith bit in the binary representation of n if the (i-1)th bit is set to 1 and the (i-2)th through 0th bits are set to 0. Return _the minimum number of operations to transform_ n _into_ 0_._ Example 1: Input: n = 3 Output: 2 Explanation: The binary representation of 3 is "11...

There are m boys and n girls in a class attending an upcoming party. You are given an m x n integer matrix grid, where grid[i][j] equals 0 or 1. If grid[i][j] == 1, then that means the ith boy can invite the jth girl to the party. A boy can invite at most one girl, and a girl can accept at most one invitation from a boy. Return _the maximum possible number of accepted invitations._ Example 1: Input: grid = \[\[1,1,1\], \[1,0,1\], \[0,0,1\]\] Output:...

You are given two identical eggs and you have access to a building with n floors labeled from 1 to n. You know that there exists a floor f where 0 <= f <= n such that any egg dropped at a floor higher than f will break, and any egg dropped at or below floor f will not break. In each move, you may take an unbroken egg and drop it from any floor x (where 1 <= x <= n). If the egg breaks, you can no longer use it. However, if the egg does not break, you m...

You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid. A uni-value grid is a grid where all the elements of it are equal. Return _the minimum number of operations to make the grid uni-value_. If it is not possible, return -1. Example 1: Input: grid = \[\[2,4\],\[6,8\]\], x = 2 Output: 4 Explanation: We can make every element equal to 4 by doing the followin...

You are playing a game with integers. You start with the integer 1 and you want to reach the integer target. In one move, you can either: * Increment the current integer by one (i.e., x = x + 1). * Double the current integer (i.e., x = 2 * x). You can use the increment operation any number of times, however, you can only use the double operation at most maxDoubles times. Given the two integers target and maxDoubles, return _the minimum number of moves nee...

You are given a positive integer num consisting of exactly four digits. Split num into two new integers new1 and new2 by using the digits found in num. Leading zeros are allowed in new1 and new2, and all the digits found in num must be used. * For example, given num = 2932, you have the following digits: two 2's, one 9 and one 3. Some of the possible pairs [new1, new2] are [22, 93], [23, 92], [223, 9] and [2, 329]. Return _the minimum poss...

You are given a 0-indexed m x n binary matrix grid. In one operation, you can choose any i and j that meet the following conditions: * 0 <= i < m * 0 <= j < n * grid[i][j] == 1 and change the values of all cells in row i and column j to zero. Return _the minimum number of operations needed to remove all_ 1_'s from_ grid_._ Example 1: Input: grid = \[\[1,1,1\],\[1,1,1\],\[0,1,0\]\] Output: 2 Explanation: In the first operation, change all c...

A bit flip of a number x is choosing a bit in the binary representation of x and flipping it from either 0 to 1 or 1 to 0. * For example, for x = 7, the binary representation is 111 and we may choose any bit (including any leading zeros not shown) and flip it. We can flip the first bit from the right to get 110, flip the second bit from the right to get 101, flip the fifth bit from the right (a leading zero) to get 10111, etc. Given two integers start and `goal...

You are given a 0-indexed m x n binary matrix matrix and an integer numSelect, which denotes the number of distinct columns you must select from matrix. Let us consider s = {c1, c2, ...., cnumSelect} as the set of columns selected by you. A row row is covered by s if: * For each cell matrix[row][col] (0 <= col <= n - 1) where matrix[row][col] == 1, col is present in s or, * No cell in row has a value of 1. You need to choose numSelect columns such...

You are given a positive integer n, you can do the following operation any number of times: * Add or subtract a power of 2 from n. Return _the minimum number of operations to make_ n _equal to_ 0. A number x is power of 2 if x == 2i where i >= 0_._ Example 1: Input: n = 39 Output: 3 Explanation: We can do the following operations: - Add 20 = 1 to n, so now n = 40. - Subtract 23 = 8 from n, so now n = 32. - Subtract 25 = 32 from n, so now n = 0. It...

There is a bag that consists of items, each item has a number 1, 0, or -1 written on it. You are given four non-negative integers numOnes, numZeros, numNegOnes, and k. The bag initially contains: * numOnes items with 1s written on them. * numZeroes items with 0s written on them. * numNegOnes items with -1s written on them. We want to pick exactly k items among the available items. Return _the maximum possible sum of numbers written on the items_. **Example ...

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position. Return true _if you can reach the last index, or_ false _otherwise_. Example 1: Input: nums = \[2,3,1,1,4\] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: nums = \[3,2,1,0,4\] Output: false Explanation: You will alway...

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. In other words, if you are at nums[i], you can jump to any nums[i + j] where: * 0 <= j <= nums[i] and * i + j < n Return _the minimum number of jumps to reach_ nums[n - 1]. The test cases are generated such that you can reach nums[n - 1]. Example 1: Input: nums = \[2,3,1,1,4\]...

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations. Given two integer arrays gas and cost, return _the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return_ -1. If ...

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive cards. Given an integer array hand where hand[i] is the value written on the ith card and an integer groupSize, return true if she can rearrange the cards, or false otherwise. Example 1: Input: hand = \[1,2,3,6,2,3,4,7,8\], groupSize = 3 Output: true Explanation: Alice's hand can be rearranged as \[1,2,3\...

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also given an integer array target = [x, y, z] that describes the triplet you want to obtain. To obtain target, you may apply the following operation on triplets any number of times (possibly zero): * Choose two indices (0-indexed) i and j (i != j) and update triplets[j] to become `[max(ai, aj), ...

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part. Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s. Return _a list of integers representing the size of these parts_. Example 1: Input: s = "ababcbacadefegdehijhklij " Output: \[9,7,8\] Explanation: The partition is "ababcbaca ", "defegde ", "hijhklij ". This is a partitio...

Given a string s containing only three types of characters: '(', ')' and '*', return true _if_ s _is valid_. The following rules define a valid string: * Any left parenthesis '(' must have a corresponding right parenthesis ')'. * Any right parenthesis ')' must have a corresponding left parenthesis '('. * Left parenthesis '(' must go before the corresponding right parenthesis ')'. * '*' could be treated as a single right parenthesis ')' or a single left pare...