# Posts tagged as “sort”

## V3

A chef has collected data on the satisfaction level of his n dishes. Chef can cook any dish in 1 unit of time.

Like-time coefficient of a dish is defined as the time taken to cook that dish including previous dishes multiplied by its satisfaction level  i.e.  time[i]*satisfaction[i]

Return the maximum sum of Like-time coefficient that the chef can obtain after dishes preparation.

Dishes can be prepared in any order and the chef can discard some dishes to get this maximum value.

Example 1:

Input: satisfaction = [-1,-8,0,5,-9]
Output: 14
Explanation: After Removing the second and last dish, the maximum total Like-time coefficient will be equal to (-1*1 + 0*2 + 5*3 = 14). Each dish is prepared in one unit of time.

Example 2:

Input: satisfaction = [4,3,2]
Output: 20
Explanation: Dishes can be prepared in any order, (2*1 + 3*2 + 4*3 = 20)


Example 3:

Input: satisfaction = [-1,-4,-5]
Output: 0
Explanation: People don't like the dishes. No dish is prepared.


Example 4:

Input: satisfaction = [-2,5,-1,0,3,-3]
Output: 35


Constraints:

• n == satisfaction.length
• 1 <= n <= 500
• -10^3 <= satisfaction[i] <= 10^3

## Solution 1: Sort+ Brute Force

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

## Solution 2: Sort + prefix sum

Sort in reverse order, accumulate prefix sum until prefix sum <= 0.

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

[9, 8, 5, 2, 1, -1]
sum = 9 * 4 + 8 * 3 + 2 * 3 + 1 * 2 + -1 * 1
<=>
sum += 9
sum += (9 + 8 = 17)
sum += (17 + 2 = 19)
sum += (19 + 1 = 20)
sum += (20 – 1 = 19)

## C++

Given two integer arrays arr1 and arr2, and the integer dreturn the distance value between the two arrays.

The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

Example 1:

Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation:
For arr1[0]=4 we have:
|4-10|=6 > d=2
|4-9|=5 > d=2
|4-1|=3 > d=2
|4-8|=4 > d=2
For arr1[1]=5 we have:
|5-10|=5 > d=2
|5-9|=4 > d=2
|5-1|=4 > d=2
|5-8|=3 > d=2
For arr1[2]=8 we have:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2


Example 2:

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2


Example 3:

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1


Constraints:

• 1 <= arr1.length, arr2.length <= 500
• -10^3 <= arr1[i], arr2[j] <= 10^3
• 0 <= d <= 100

## Solution 1: All pairs

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

## Solution 2: Two Pointers

Sort arr1 in ascending order and sort arr2 in descending order.
Time complexity: O(mlogm + nlogn + m + n)
Space complexity: O(1)

## Solution 3: Binary Search

Sort arr2 in ascending order. and do two binary searches for each element to determine the range of [a-d, a+d], if that range is empty we increase the counter

Time complexity: O(mlogm + nlogm)
Space complexity: O(1)

## C++

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j's such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:

Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).


Example 2:

Input: nums = [6,5,4,8]
Output: [2,1,0,3]


Example 3:

Input: nums = [7,7,7,7]
Output: [0,0,0,0]


Constraints:

• 2 <= nums.length <= 500
• 0 <= nums[i] <= 100

## Solution 1: Brute Force

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

## Solution 2: Sort + Binary Search

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

## Solution 3: Cumulative frequency

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

## C++

Given an integer array arr. You have to sort the integers in the array in ascending order by the number of 1’s in their binary representation and in case of two or more integers have the same number of 1’s you have to sort them in ascending order.

Return the sorted array.

Example 1:

Input: arr = [0,1,2,3,4,5,6,7,8]
Output: [0,1,2,4,8,3,5,6,7]
Explantion: [0] is the only integer with 0 bits.
[1,2,4,8] all have 1 bit.
[3,5,6] have 2 bits.
[7] has 3 bits.
The sorted array by bits is [0,1,2,4,8,3,5,6,7]


Example 2:

Input: arr = [1024,512,256,128,64,32,16,8,4,2,1]
Output: [1,2,4,8,16,32,64,128,256,512,1024]
Explantion: All integers have 1 bit in the binary representation, you should just sort them in ascending order.


Example 3:

Input: arr = [10000,10000]
Output: [10000,10000]


Example 4:

Input: arr = [2,3,5,7,11,13,17,19]
Output: [2,3,5,17,7,11,13,19]


Example 5:

Input: arr = [10,100,1000,10000]
Output: [10,100,10000,1000]


Constraints:

• 1 <= arr.length <= 500
• 0 <= arr[i] <= 10^4

## Solution: Sorting

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