Press "Enter" to skip to content

Posts tagged as “sort”

花花酱 LeetCode 853. Car Fleet

N cars are going to the same destination along a one lane road.  The destination is target miles away.

Each car i has a constant speed speed[i] (in miles per hour), and initial position position[i] miles towards the target along the road.

A car can never pass another car ahead of it, but it can catch up to it, and drive bumper to bumper at the same speed.

The distance between these two cars is ignored – they are assumed to have the same position.

car fleet is some non-empty set of cars driving at the same position and same speed.  Note that a single car is also a car fleet.

If a car catches up to a car fleet right at the destination point, it will still be considered as one car fleet.


How many car fleets will arrive at the destination?

Example 1:

Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
Explanation:
The cars starting at 10 and 8 become a fleet, meeting each other at 12.
The car starting at 0 doesn't catch up to any other car, so it is a fleet by itself.
The cars starting at 5 and 3 become a fleet, meeting each other at 6.
Note that no other cars meet these fleets before the destination, so the answer is 3.


Note:

  1. 0 <= N <= 10 ^ 4
  2. 0 < target <= 10 ^ 6
  3. 0 < speed[i] <= 10 ^ 6
  4. 0 <= position[i] < target
  5. All initial positions are different.

Solution: Greedy

  1. Compute the time when each car can reach target.
  2. Sort cars by position DESC

Answer will be number slow cars in the time array.

Ex 1: 
target = 12
p = [10,8,0,5,3] 
v = [2,4,1,1,3]


p     t
10    1  <- slow -- ^
 8    1             |
 5    7  <- slow -- ^
 3    3             |
 0   12  <- slow -- ^

Ex 2
target = 10
p = [5, 4, 3, 2, 1]
v = [1, 2, 3, 4, 5]

p     t
5     5  <- slow -- ^
4     3             |
3     2.33          |
2     2             |
1     1.8           |

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

C++

Python3

花花酱 LeetCode 976. Largest Perimeter Triangle

Given an array A of positive lengths, return the largest perimeter of a triangle with non-zero area, formed from 3 of these lengths.

If it is impossible to form any triangle of non-zero area, return 0.

Example 1:

Input: [2,1,2]
Output: 5

Example 2:

Input: [1,2,1]
Output: 0

Example 3:

Input: [3,2,3,4]
Output: 10

Example 4:

Input: [3,6,2,3]
Output: 8

Note:

  1. 3 <= A.length <= 10000
  2. 1 <= A[i] <= 10^6

Solution: Greedy

Answer must be 3 consecutive numbers in the sorted array
if A[i] >= A[i+1] + A[i+2], then A[i] >= A[i+j] + A[i+k], 1 < j < k
if A[i] < A[i+1] + A[i+2], then A[i] + A[i+1] + A[i+2] is the answer

C++

花花酱 LeetCode 969. Pancake Sorting

Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A.  We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A.  Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Example 1:

Input: [3,2,4,1]
Output: [4,2,4,3]
Explanation: 
We perform 4 pancake flips, with k values 4, 2, 4, and 3.
Starting state: A = [3, 2, 4, 1]
After 1st flip (k=4): A = [1, 4, 2, 3]
After 2nd flip (k=2): A = [4, 1, 2, 3]
After 3rd flip (k=4): A = [3, 2, 1, 4]
After 4th flip (k=3): A = [1, 2, 3, 4], which is sorted. 

Example 2:

Input: [1,2,3]
Output: []
Explanation: The input is already sorted, so there is no need to flip anything.
Note that other answers, such as [3, 3], would also be accepted.

Note:

  1. 1 <= A.length <= 100
  2. A[i] is a permutation of [1, 2, ..., A.length]

Solution: Simulation

Put the largest element to its position. Each element requires two flips
e.g. [3, 2, 4, 1]
largest element: 4, index: 2
flip1: [4, 2, 3, 1]
flip2: [1, 3, 2, 4]
Repeat for [1, 3, 2]…

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

C++

花花酱 LeetCode 945. Minimum Increment to Make Array Unique

Problem

Given an array of integers A, a move consists of choosing any A[i], and incrementing it by 1.

Return the least number of moves to make every value in A unique.

Example 1:

Input: [1,2,2]
Output: 1
Explanation:  After 1 move, the array could be [1, 2, 3].

Example 2:

Input: [3,2,1,2,1,7]
Output: 6
Explanation:  After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

Note:

  1. 0 <= A.length <= 40000
  2. 0 <= A[i] < 40000

Solution: Greedy

Sort the elements, make sure A[i] >= A[i-1] + 1, if not increase A[i] to A[i – 1] + 1

Time complexity: O(nlogn)

Space complexity: O(1)

C++

Python3

 

花花酱 LeetCode 937. Reorder Log Files

Problem

https://leetcode.com/problems/reorder-log-files/description/

You have an array of logs.  Each log is a space delimited string of words.

For each log, the first word in each log is an alphanumeric identifier.  Then, either:

  • Each word after the identifier will consist only of lowercase letters, or;
  • Each word after the identifier will consist only of digits.

We will call these two varieties of logs letter-logs and digit-logs.  It is guaranteed that each log has at least one word after its identifier.

Reorder the logs so that all of the letter-logs come before any digit-log.  The letter-logs are ordered lexicographically ignoring identifier, with the identifier used in case of ties.  The digit-logs should be put in their original order.

Return the final order of the logs.

Example 1:

Input: ["a1 9 2 3 1","g1 act car","zo4 4 7","ab1 off key dog","a8 act zoo"]
Output: ["g1 act car","a8 act zoo","ab1 off key dog","a1 9 2 3 1","zo4 4 7"]

Note:

  1. 0 <= logs.length <= 100
  2. 3 <= logs[i].length <= 100
  3. logs[i] is guaranteed to have an identifier, and a word after the identifier.

Solution: Partition + Sort

  1. partition the array such that all digit logs are after all letter logs
  2. sort the letter logs part based on the log content

Time complexity: O(n + aloga)

Space complexity: O(n)

C++