Press "Enter" to skip to content

Posts tagged as “sort”

花花酱 LeetCode 628. Maximum Product of Three Numbers

Problem

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

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

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

Idea:

Find the top 3 numbers t1, t2, t3, and bottom 2 numbers, b1, b2.

If all numbers are positives,  answer must be t1 * t2 * t3.

Since the number can go negative, the answer must be either t1*t2*t3 or b1 * b2 * t1, if b1 and b2 are both negatives.

ex. nums: [5, 1, -6, 3, -1]

t1, t2, t3: 5, 3, 1

b1, b2: -6, -1

t1 * t2 * t3 = 15

t1 * b1 * b2 = 30

Solution 1: Manual Tracking

Time complexity: O(n)

Space complexity: O(1)

Solution 2: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

Solution 3: Two Heaps (Priority Queues)

Time complexity: O(nlog3)

Space complexity: O(2 + 3)

 

花花酱 LeetCode 148. Sort List

Problem

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

Solution: Merge Sort

Top-down (recursion)

Time complexity: O(nlogn)

Space complexity: O(logn)

C++

Java

Python3

 

bottom up

Time complexity: O(nlogn)

Space complexity: O(1)

花花酱 LeetCode 192. Word Frequency

Write a bash script to calculate the frequency of each word in a text file words.txt.

For simplicity sake, you may assume:

  • words.txt contains only lowercase characters and space ' ' characters.
  • Each word must consist of lowercase characters only.
  • Words are separated by one or more whitespace characters.

For example, assume that words.txt has the following content:

the day is sunny the the
the sunny is is

Your script should output the following, sorted by descending frequency:

the 4
is 3
sunny 2
day 1

Note:
Don’t worry about handling ties, it is guaranteed that each word’s frequency count is unique.

Solution

bash

花花酱 LeetCode 56. Merge Intervals

Problem:

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].



Idea:

Sweep line

Solution:

C++

Python

 

Related Problems:

花花酱 LeetCode 451. Sort Characters By Frequency

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

Example 2:

Example 3:

Solution: