Press "Enter" to skip to content

Posts tagged as “greedy”

花花酱 LeetCode 1505. Minimum Possible Integer After at Most K Adjacent Swaps On Digits

Given a string num representing the digits of a very large integer and an integer k.

You are allowed to swap any two adjacent digits of the integer at most k times.

Return the minimum integer you can obtain also as a string.

Example 1:

Input: num = "4321", k = 4
Output: "1342"
Explanation: The steps to obtain the minimum integer from 4321 with 4 adjacent swaps are shown.

Example 2:

Input: num = "100", k = 1
Output: "010"
Explanation: It's ok for the output to have leading zeros, but the input is guaranteed not to have any leading zeros.

Example 3:

Input: num = "36789", k = 1000
Output: "36789"
Explanation: We can keep the number without any swaps.

Example 4:

Input: num = "22", k = 22
Output: "22"

Example 5:

Input: num = "9438957234785635408", k = 23
Output: "0345989723478563548"

Constraints:

  • 1 <= num.length <= 30000
  • num contains digits only and doesn’t have leading zeros.
  • 1 <= k <= 10^9

Solution: Greedy + Recursion (Update: TLE after 7/6/2020)

Move the smallest number to the left and recursion on the right substring with length equals to n -= 1.

4321 k = 4 => 1 + solve(432, 4-3) = 1 + solve(432, 1) = 1 + 3 + solve(42, 0) = 1 + 3 + 42 = 1342.

Time complexity: O(n^2)
Space complexity: O(1)

C++

Solution 2: Binary Indexed Tree / Fenwick Tree

Moving elements in a string is a very expensive operation, basically O(n) per op. Actually, we don’t need to move the elements physically, instead we track how many elements before i has been moved to the “front”. Thus we know the cost to move the i-th element to the “front”, which is i – elements_moved_before_i or prefix_sum(0~i-1) if we mark moved element as 1.

We know BIT / Fenwick Tree is good for dynamic prefix sum computation which helps to reduce the time complexity to O(nlogn).

Time complexity: O(nlogn)
Space complexity: O(n)

C++

Java

Python3

花花酱 LeetCode 1481. Least Number of Unique Integers after K Removals

Given an array of integers arr and an integer k. Find the least number of unique integers after removing exactly k elements.

Example 1:

Input: arr = [5,5,4], k = 1
Output: 1
Explanation: Remove the single 4, only 5 is left.

Example 2:

Input: arr = [4,3,1,1,3,3,2], k = 3
Output: 2
Explanation: Remove 4, 2 and either one of the two 1s or three 3s. 1 and 3 will be left.

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 10^9
  • 0 <= k <= arr.length

Solution: Greedy

Count the frequency of each unique number. Sort by frequency, remove items with lowest frequency first.

Time complexity: O(nlogn)
Space complexity: O(n)

C++

花花酱 LeetCode 1477. Find Two Non-overlapping Sub-arrays Each With Target Sum

Given an array of integers arr and an integer target.

You have to find two non-overlapping sub-arrays of arr each with sum equal target. There can be multiple answers so you have to find an answer where the sum of the lengths of the two sub-arrays is minimum.

Return the minimum sum of the lengths of the two required sub-arrays, or return -1 if you cannot find such two sub-arrays.

Example 1:

Input: arr = [3,2,2,4,3], target = 3
Output: 2
Explanation: Only two sub-arrays have sum = 3 ([3] and [3]). The sum of their lengths is 2.

Example 2:

Input: arr = [7,3,4,7], target = 7
Output: 2
Explanation: Although we have three non-overlapping sub-arrays of sum = 7 ([7], [3,4] and [7]), but we will choose the first and third sub-arrays as the sum of their lengths is 2.

Example 3:

Input: arr = [4,3,2,6,2,3,4], target = 6
Output: -1
Explanation: We have only one sub-array of sum = 6.

Example 4:

Input: arr = [5,5,4,4,5], target = 3
Output: -1
Explanation: We cannot find a sub-array of sum = 3.

Example 5:

Input: arr = [3,1,1,1,5,1,2,1], target = 3
Output: 3
Explanation: Note that sub-arrays [1,2] and [2,1] cannot be an answer because they overlap.

Constraints:

  • 1 <= arr.length <= 10^5
  • 1 <= arr[i] <= 1000
  • 1 <= target <= 10^8

Solution: Sliding Window + Best so far

  1. Use a sliding window to maintain a subarray whose sum is <= target
  2. When the sum of the sliding window equals to target, we found a subarray [s, e]
  3. Update ans with it’s length + shortest subarray which ends before s.
  4. We can use an array to store the shortest subarray which ends before s.

Time complexity: O(n)
Space complexity: O(n)

C++

花花酱 LeetCode 1414. Find the Minimum Number of Fibonacci Numbers Whose Sum Is K

Given the number kreturn the minimum number of Fibonacci numbers whose sum is equal to k, whether a Fibonacci number could 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 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 + 5 = 7.

Example 2:

Input: k = 10
Output: 2 
Explanation: For k = 10 we can use 2 + 8 = 10.

Example 3:

Input: k = 19
Output: 3 
Explanation: For k = 19 we can use 1 + 5 + 13 = 19.

Constraints:

  • 1 <= k <= 10^9

Solution: Greedy

Find the largest fibonacci numbers x that x <= k, ans = 1 + find(k – x)

Time complexity: O(logk^2) -> O(logk)
Space complexity: O(logk) -> O(1)

Recursive

C++

Iterative

C++

花花酱 LeetCode 1405. Longest Happy String

A string is called happy if it does not have any of the strings 'aaa''bbb' or 'ccc' as a substring.

Given three integers ab and c, return any string s, which satisfies following conditions:

  • s is happy and longest possible.
  • s contains at most a occurrences of the letter 'a'at most b occurrences of the letter 'b' and at most c occurrences of the letter 'c'.
  • will only contain 'a''b' and 'c' letters.

If there is no such string s return the empty string "".

Example 1:

Input: a = 1, b = 1, c = 7
Output: "ccaccbcc"
Explanation: "ccbccacc" would also be a correct answer.

Example 2:

Input: a = 2, b = 2, c = 1
Output: "aabbc"

Example 3:

Input: a = 7, b = 1, c = 0
Output: "aabaa"
Explanation: It's the only correct answer in this case.

Constraints:

  • 0 <= a, b, c <= 100
  • a + b + c > 0

Solution: Greedy

Put the char with highest frequency first if its consecutive length of that char is < 2
or put one char if any of other two chars has consecutive length of 2.

increase the consecutive length of itself and reset that for other two chars.

Time complexity: O(n)
Space complexity: O(1)

C++