# Posts tagged as “sorting”

Problem:

https://leetcode.com/problems/intersection-of-two-arrays/description/

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1]nums2 = [2, 2], return [2].

Note:

• Each element in the result must be unique.
• The result can be in any order.

C++ using std::set_intersection

C++ hashtable

Problem:

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

Note:

1. N is a positive integer and won’t exceed 10,000.
2. All the scores of athletes are guaranteed to be unique.

Solution 1: Sorting ( + Binary Search)

C++

S and T are strings composed of lowercase letters. In S, no letter occurs more than once.

S was sorted in some custom order previously. We want to permute the characters of T so that they match the order that S was sorted. More specifically, if x occurs before y in S, then x should occur before y in the returned string.

Return any permutation of T (as a string) that satisfies this property.

Note:

• S has length at most 26, and no character is repeated in S.
• T has length at most 200.
• S and T consist of lowercase letters only.

Solution 1: HashTable + Sorting

1. Store the order of char in a hashtable
2. Sort the string based on the order

Time complexity: O(nlogn)

Space complexity: O(128)

Given an array arr that is a permutation of [0, 1, ..., arr.length - 1], we split the array into some number of “chunks” (partitions), and individually sort each chunk.  After concatenating them, the result equals the sorted array.

What is the most number of chunks we could have made?

Example 1:

Example 2:

Note:

• arr will have length in range [1, 10].
• arr[i] will be a permutation of [0, 1, ..., arr.length - 1].

Solution 1: Max so far / Set

Time complexity: O(nlogn)

Space complexity: O(n)

C++

Solution 2: Max so far

Time complexity: O(n)

Space complexity: O(1)

C++

Java

Python3

Problem:

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

Examples:

[2,3,4] , the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Your job is to output the median array for each window in the original array.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Therefore, return the median sliding window as [1,-1,-1,3,5,6].

Note:
You may assume k is always valid, ie: k is always smaller than input array’s size for non-empty array.

Solution 0: Brute Force

Time complexity: O(n*klogk) TLE 32/42 test cases passed

Solution 1: Insertion Sort

Time complexity: O(k*logk +  (n – k + 1)*k)

Space complexity: O(k)

C++ / vector

C++ / vector + binary_search for deletion.

Java

Java / Binary Search

Python

Solution 2: BST

Related Problems: