Shortest Subarray with Sum at Least K

Problem

Shortest Subarray with Sum at Least K

Return the length of the shortest, non-empty, contiguous subarray of A with sum at least K.

If there is no non-empty subarray with sum at least K, return -1.

Example 1:

Input: A = [2,-1,2], K = 3

Output: 3

Input: A = [1,2], K = 4

Output: -1

Example 3

Input: A= [2,-1,1,2,-1,2,2,-1,-2], K = 5
Output: 4

Note:

1 <= A.length <= 50000

-10 ^ 5 <= A[i] <= 10 ^ 5

1 <= K <= 10 ^ 9

Solution

The brutal force way is, for 0 to N, for each index, search on the right for the first subarray sum at least K. After go through all the indexes, we return the shortest Subarray that with sum at least K. The cost is O(N^2).

A slightly better brutal force solution is to try 1 element combinations, then 2 element combinations, then 3 element combinations, until we found solution then exit, or go through all the possible scenarios, then return -1. The cost is still O(N^2), but may exit earlier than the other brutal force with luck.

A better solution can find the answer in O(N) if we step back and think about what we are doing.
This problem is equivalent to an investment problem on stock market. The array is the every day gain and loss. The problem is to find the buy day and sell day for a stock, in order to achieve gain higher than K. The gain between day i and day j is the sum(j) - sum(i). Our goal is to achieve the target gain in the shortest time possible.

stock price

With some common sense, we know the stock price has up and downs. In order to achieve the gain in shortest time possible, we will never trade at the down slope. For buying stock, if we buy at down slope, we start to loose money right away. We would rather wait for the down slope is over, then we buy. In that case, we enter later but achieve the target gain earlier. Simply because if we enter later, our net gain that day is 0 instead of negative! The sell can only happen at uphill as well. If we could sell at a downhill and still have gain larger than K, why not sell it earlier, when the price is higher? Another observation is, we buy at day A, as soon as the gain K is reached at day B, we want to sell immediately. Waiting longer won't help our goal, there is no shorter period of get back our investment than right now.  With these observations, we can code as if we are trading the stock. 

One more detail, the first day is uphill or down hill is decided by comparing to 0. Positive is uphill, negative is downhill. That is the reason we have sum array with size N+1 instead of N.

import java.util.*;
public class InvestmentCycle {
  public static int shortest(int[] a, int gain) {//2,-1,2
    int N = a.length;
    Deque<Integer> deque = new LinkedList<>();
    int[] sum = new int[a.length+1];
    int min = N+1;
    for(int i = 0; i < a.length; i++) {
      sum[i+1] = sum[i] + a[i];//{0, 2, 1, 3}
    }
    for(int i = 0; i < sum.length; i++) {
      if(i > 0 && sum[i] <= sum[i-1]) {continue;} //don't sell at downhill
      while(!deque.isEmpty() && sum[i] <= sum[deque.getLast()]) { //don't buy at downhill
        deque.removeLast();
      }
      while(!deque.isEmpty() && sum[i] - sum[deque.getFirst()] >= gain) {
        min = Math.min(min, i - deque.removeFirst());//no better opportunity later with this start date
      }
      deque.addLast(i);//next start date to consider
    }
    return (min == N+1)?-1:min;
  }
  public static void main(String...args) {
    System.out.println(shortest(new int[]{2,-1,2}, 3));
    System.out.println(shortest(new int[]{1,2}, 4));
    System.out.println(shortest(new int[]{2,-1,1,2,-1,2,2,-1-2}, 5));
    System.out.println(shortest(new int[]{1}, 1));
  }
}

The time cost is O(N) and the space cost is O(N) as well.

Problem

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.

Example: 

Input: s = 7, nums = [2,3,1,2,4,3]

Output: 2

Explanation: the subarray [4,3] has the minimal length under the problem constraint.

Solution

We use 2 pointers for left and right end of the subarray. Increasing right pointer will increase sum, and increasing left pointer will decrease sum. We start at index 0 for both left and right pointer. Then we increase right. As soon as we get a subarray that is bigger than s, we decrease the sum by increasing left until the subarray no longer qualify. Then we increase right to make it qualify again, then we shrink the size until it is no longer qualify. That way, we find the answer in O(N) time with O(1) space cost. The left pointer and right pointer never across, so we have scanned all the possible subarrays with sum bigger than s.

public class MinSizeSubArraySum {
  public static int minSize(int[] a,int s) {//7
    //2,3,1,2,4,3
    //          .
    int N = a.length; //6
    int minSize = Integer.MAX_VALUE;
    int lo = 0;//4
    int sum = 0;
    for(int i = 0; i < N; i++) { //5
      sum += a[i];  //3
      while(sum >= s) {
        minSize = Math.min(minSize, i - lo + 1);//2
        sum = sum - a[lo++]; //3
      }
    }
    return (minSize == Integer.MAX_VALUE) ? 0 : minSize;
  }
  public static void main(String[] args) {
    System.out.println(minSize(new int[]{2,3,1,2,4,3}, 7));
    System.out.println(minSize(new int[]{1,1,1,2}, 7));
  }
}

Time complexity O(N), space complexity O(1).

Find Minimum in Rotated Sorted Array

Problem

Find Minimum in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e.,  [0,1,2,4,5,6,7] might become  [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

Input: [3,4,5,1,2] 

Output: 1

Example 2:

Input: [4,5,6,7,0,1,2]

Output: 0

Solution

This is an edge detection problem, the brutal force way is to check the first occurrence of a[i-1] > a[i]. The time cost will be O(N).

With binary search, the cost can be cut down to O(logN). The middle could land on the left of the edge or right of the edge. We also need to consider special cases when the array is not rotating, the array has only one element. 

public class MinInRotatedArray {
  public static int min(int[] a) {
    //3,4,5,6,7,0,1,2
    //        * .   
    int N = a.length;//8
    int lo = 0;
    int hi = N - 1;
    if(a[lo] <= a[hi]) return a[lo];
   
    int mid = 0;
    while(lo < hi) {//4,7
      mid = lo + (hi - lo)/2;//5
      if(mid > 0 && a[mid] < a[mid - 1]) {
        return a[mid];
      } else if(mid < N - 1 && a[mid] > a[mid+1]) {
        return a[mid+1];
      }
      if(a[lo] < a[mid]) lo = mid + 1;
      else if(a[lo] > a[mid]) {
        hi = mid - 1;
      }
      else return a[mid];
    }
    return a[mid];
  }
  public static void main(String...args) {
    System.out.println(min(new int[]{3,4,5,6,7,0,1,2}));
    System.out.println(min(new int[]{3,4,5,6,7,0,1,2}));
    System.out.println(min(new int[]{5,6,7,0,1,2,3,4}));
    System.out.println(min(new int[]{0,1,2,3,4,5,6,7}));
    System.out.println(min(new int[]{7,0,1,2,3,4,5,6}));
    System.out.println(min(new int[]{1,2,3,4,5,6,7,0}));
    System.out.println(min(new int[]{0}));
  }
}

Time cost O(logN), space cost O(1).

Intersection of Two Arrays II

Problem

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]

Output: [2,2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]

Output: [4,9]

Note:

Each element in the result should appear as many times as it shows in both arrays.

The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?

What if nums1's size is small compared to nums2's size? Which algorithm is better?

What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

Solution

One solution is to sort the arrays, then use 2 pointers to find the solution. The time cost is O(NlogN + MlogM), the space cost is O(1).

import java.util.*;
public class InterSection  {
  public static List<Integer> findInterSection(int[] a, int[] b) {
    //[4 5 9], nums2 = [4 4 8 9 9]
    Arrays.sort(a);
    Arrays.sort(b);
    List<Integer> result = new ArrayList<>();
    int N = a.length; //3
    int M = b.length;  //5
    int i = 0, j = 0;
    while(i < N && j < M) {
      if(a[i] < b[j]) i++; //2
      else if(a[i] > b[j]) j++; //3
      else {
        result.add(a[i]); //4 9
        i++;  //3
        j++;  //4
      }
    }
    return result;
  }
  public static void main(String...args) {
    int[] a = new int[]{1,2,2,1};
    int[] b = new int[]{2,2};
    for(int i : findInterSection(a, b)) {
      System.out.print(" " + i);
    }
  }
}

Another solution is to use a hash map to store the character count in array 1, then go through the array 2, add the elements that exist in the hash map and decrease the count. When the count decrease to 0, we need to remove the element. 

The time cost will be O(M + N), the space cost is O(M)

Merge Intervals

Problem

Given a collection of intervals, merge all overlapping intervals.

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Solution

If the arrays is sorted by the first elements, then we can scan through the arrays. For the current array, if the left boundary is within the previous array's range, we merge the current array with the previous array, otherwise we add the previous array to solution set, then replace the previous array with the current array. The cost will be O(N) and space is O(1). If we need to sort the arrays, the cost will be O(NlogN).

import java.util.*;
public class MergeIntervals {
  private static class ArrayComparator implements Comparator<int[]> {
    public int compare(int[] a, int[] b) {
      return a[0] - b[0];
    }
  }
  public static List<int[]> intervalsMerge(int[][] arrs) {
    Collections.sort(Arrays.asList(arrs), new ArrayComparator());
    //{1,3},{2,6},{8,10},{15,18}
    int[] pre = arrs[0]; //15 18
    List<int[]> result = new ArrayList<>(); //1, 6; 1 10;
    for(int i = 1; i < arrs.length; i++) {
      int[] cur = arrs[i]; //15 18
      if(pre[1] < cur[0]) { //
        result.add(pre);
        pre = cur;
      } else {
        pre[1] = cur[1];  //
      }
    }
    result.add(pre);
    return result;
  }
  public static void main(String...args) {
    int[][] arrs = new int[][] {
      {1,3},{2,6},{8,10},{15,18}
    };
    for(int[] arr : intervalsMerge(arrs)) {
      System.out.println("[" + arr[0] + " " + arr[1] + "]");
    }
  }
}

Time cost O(NlogN), space cost O(1)

Another approach is similar to Meeting Rooms II. We can sort all the start and end points. Then we iterate them, whenever count is 0, we add a range to the result -- we got an end point also register a new start point. A previous registered start point and current end point form a range to be added to the result.

Sort An Increasing-Decreasing Array

Problem

An array's elements repeatedly increase up to a certain index after which they decrease to a small value, then again increase. This repeated k times.
for example, given array {1, 2, 3, 1, 2, 4, 5, 1, 3, 4}, the output should be
{1, 1, 1, 2, 2, 3, 3, 4, 4, 5}

Solution

Fasted sort uses time cost NlogN to sort the array. However, this array is partially sorted. We can use N step to find all the boundaries or the increasing sub-arrays, then we can use priority queue to decide which subarray should provide the next element. The time cost is O(N + N*klogk) which is dominant by O(Nklogk), when k is small, klogk is smaller than logN. The space cost is O(N), we need to create a new array, it is not in place sort.

import java.util.*;
public class KInDeArrays {
  //123 1245 134
  //           .
  //0 - [0, 2, 0, 0], 1 - [3, 6, 3, 1], 2 - [7, 9, 7, 2],
  //false
  public static Map<Integer, int[]> findBoundary(int[] a) {
    Map<Integer, int[]> kArrays = new HashMap<>();
    int k = 0;
    boolean isStart = true;
    for(int i = 0; i < a.length; i++) {
      if(i == 0 || a[i-1] > a[i]) {
          isStart = true;
      }
      if(isStart) {
        int[] arr = kArrays.get(k);  //1
        if(arr == null) {
          kArrays.put(k, new int[]{i, i, i});
          isStart = false;
        } else {
          arr[1] = i - 1;
          kArrays.put(++k, new int[]{i, i, i});
          isStart = false;
        }
      }
    }
    int[] arr = kArrays.get(k);
    arr[1] = a.length - 1;
    return kArrays;
  }
  //0 - [0, 2, 0], 1 - [3, 6, 3], 2 - [7, 9, 7],
  //
  public static int[] sort(int[] a, Map<Integer, int[]> boundaries) {
    Queue<int[]> pq = new PriorityQueue<>(boundaries.size(), (i, j) -> a[i[2]] - a[j[2]]);
    for(int[] arr : boundaries.values()) {
      pq.add(arr);   //    [7, 9, 7] [0, 2, 2]  [3, 6, 4]
    }
    int r = 0;//{1, 2, 3,  1, 2, 4, 5,  1, 3, 4}
    int[] result = new int[a.length]; //[1,...2, ]
    while(!pq.isEmpty()) {
      int[] arr = pq.poll();
      result[r++] = a[arr[2]]; //1
      int curIndex = arr[2];
      if(curIndex < arr[1]) {
        arr[2] = curIndex + 1;
        pq.add(arr);
      }
    }
    return result;
  }
 
  public static void main(String...args) {
    int[] a = {1, 2, 3, 1, 2, 4, 5, 1, 3, 4};
    int[] result = sort(a, findBoundary(a));
    Arrays.stream(result).forEach(i -> System.out.print(" " + i));
  }
}

Time cost O(Nklogk), space cost O(N). 

Merge A List Of Sorted Arrays

Problem

Merge A List Of Sorted Arrays

Write a program that takes as input a set of sorted sequences and computes the union of these sequences as a sorted sequence. For example, if the input is [3, 5, 7], [0, 6], and [0, 6, 28], then the output is [0, 0, 3, 5, 6, 6, 7, 28].

Solution

The problem is asking for general solution, though we can start with 3 array cases, but eventually the solution should handle N array. 

Brutal force solution is to copy them all into a new array, then run NlongN sort. However, since the arrays are sorted, we only need k pointers to trace which array has the smallest element compare to the rest of the k - 1. We can use a priority queue to keep track of the smallest element. Priority queue use heap sort to support O(1) cost smallest element retrieval, with k sized priority queue, the sink and swim operation cost is klogk. So the total time cost will be Nklogk, the extra space cost is O(k) which is the space occupied by the priority queue.

import java.util.*;

public class MergeSortedArrays {

  public static int[] sort(int[][] arrays) {

    //[3, 5, 7], [0, 6], and [0, 6, 28]

    int k = arrays.length;  //3

    int N = 0;   

    for(int[] array : arrays) {

      N += array.length;

    }

    int[] result = new int[N]; //8

    int r = 0;

    Queue<int[]> pq = new PriorityQueue<>(k, (i, j) -> arrays[i[0]][i[1]]-arrays[j[0]][j[1]]);

    for(int i = 0; i < arrays.length; i++) {

      pq.offer(new int[]{i, 0});  //  2 1, 0 2

    }

    while(!pq.isEmpty()) {

      int[] t = pq.poll(); //1 1

      int arrSeq = t[0];

      int curIndex = t[1];

      result[r++] = arrays[arrSeq][curIndex]; //[0, 0, 3, 5, 6]

      if(curIndex < arrays[arrSeq].length - 1) {

        pq.offer(new int[]{arrSeq, ++curIndex});

      }

    }

    return result;

  }

  

  public static void main(String...args) {

    int[][] arrays = new int[][] {

      {3, 5, 7},

      {0, 6},

      {0, 6, 28}

    };

    int[] result = sort(arrays);

    System.out.println(result.length);

    Arrays.stream(result).forEach(i -> System.out.print(i + " "));

  }

}

Time cost O(Nklogk), extra space O(k)

Merge k sorted linked lists

Problem

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:

[

  1->4->5,

  1->3->4,

  2->6

]

Output: 1->1->2->3->4->4->5->6

Solution

brutal force solution is to traversal all the linked lists, create an array, sort the array, then create a new linked list.

The time cost is O(NlogN), space cost is O(N)

we can also put the first k nodes into a priority queue, then take one at a time, push the next into the queue until done.

import java.util.*;
class KLinkedListsMerge {
  public static Node merge(Node[] nodes) {
    Node kHead = new Node(-1, null);
    Node tail = kHead;
    PriorityQueue<Node> pq = new PriorityQueue<>((i, j) -> i.value - j.value);
    for(Node head : nodes)
      pq.add(head);
    while(!pq.isEmpty()) {
      Node head = pq.poll();
      if(head.next != null)
        pq.add(head.next);
      head.next = null;
      tail.next = head;
      tail = head;
    }
    return kHead;
  }
  private static class Node {
    int value;
    Node next;
    public Node(int value, Node next) {
      this.value = value;
      this.next = next;
    }
  }
  public static void main(String...args) {
    Node[] nodes = new Node[3];
    //1->4->5
    nodes[0] = new Node(1, new Node(4, new Node(5, null)));
    nodes[1] = new Node(1, new Node(3, new Node(4, null)));
    nodes[2] = new Node(2, new Node(6, null));
    Node head = merge(nodes);
    head = head.next;
    while(head.next != null) {
      System.out.print(head.value + " -> ");
      head = head.next;
    }
    System.out.println("null");
  }
}

The time cost is bounded by the priority queue, the queue size is k after initialization, then add each element need logk time to restore the order. The total time cost is O(Nlogk). Space cost is the O(k) which is the priority queue size.

minimum value in stack

Problem

Find the minimum value in a stack with O(1) time complexity.

Solution

Iterate through the stack elements for the minimum value takes O(N), won't satisfy the criteria. The only way to make it work is to have the minimum value stored so that we can return it in instant time. How to store the minimum value? A variable won't work. Once we pop out the min value, we won't be able to know what is the next minimum value in the stack. We need to store a sequence of minimum values in a stack or queue. We are not clear what should be stored, so let's play with an example. 

push 3, 5, 7, 2, 5

when push 3, we record 3 as min.

when push 5, 7, we don't care, they are larger anyway.

when push 2, we got a new min, so we store 2 above 3, that tells us we need a stack as the storage.

when push 5, we don't care.

Now we got two stacks:

value stack:   5, 2, 7, 5, 3    

min stack:     2, 3

Now let's pop the value stack. 

pop 5, we don't care, it didn't change min value.

pop 2, our min value changes, so we also pop 2 from the min stack.

pop 7, 5 we don't care.

pop 3, the min value changes, so we pop 3 from the min stack.

Coding the above is straight forward.

//[5, 3, 3, 7, 2, 8]
//3 3 5
//3 3 5
import java.util.*;
class FastMinStack {
  private Stack<Integer> values = new Stack<>();
  private Stack<Integer> mins = new Stack<>();
  public int getMin() {
    if(mins.isEmpty()) throw new RuntimeException("stack is empty");
    return mins.peek();
  }
  public void pop() {
    int val = values.pop();
    if(val == mins.peek()) mins.pop();
    return val;
  }
  public int push(int val) {
    values.push(val);
    if(mins.isEmpty() || val <= mins.peek())
      mins.push(val);
  }
  public static void main(String[] args) {
    FastMinStack fms = new FastMinStack();
    fms.push(5);
    fms.push(3);
    fms.push(3);
    fms.push(7);
    fms.push(2);
    fms.push(8);
    System.out.println(fms.getMin());//2
    fms.pop();
    System.out.println(fms.getMin());//2
    fms.pop();
    System.out.println(fms.getMin());//3
    fms.pop();
    fms.pop();
    System.out.println(fms.getMin());//3
    fms.pop();
    System.out.println(fms.getMin());//5
  }
}

The time complexity is O(1) for getMin, the space cost is O(N) in worst case, where the stack is 5 4 3 2 1, we have to store all of them for min values.

Find Kth smallest number

Problem

Given an integer array, find the Kth smallest number in the array.
For example, given array {3, 0, -1, 0, 8, 7}, the 3rd smallest number is 0.

Solution

Solution 1:

We can sort the array with cost NlogN, then the Kth smallest number is at index K - 1.

Solution 2:
We can iterate the array 3 times, the first time, we find the smallest value.
The second time, if the current value equal to the smallest value we found last time, we ignore it, then continue to find the next smallest value.
The third time, if the current value matches any of the 2 smallest values we already saw, we  ignore the position, continue to find the 3rd smallest value.
After k loops, we found the Kth smallest value. The time complexity is O(KN).

Solution 3:

We can iterate the array once, find the smallest K numbers, then the largest in those K numbers are the solution. The cost is O(N).

If K = 3

we set r1 = r2 = r3 = Integer.MAX_VALUE before start traversal the array. Name current array value t.

    r1   r2    r3

  t         

if t <= r1

    r3 = r2

    r2 = r1

    r1 = t

else if t <= r2

    r3 = r2

    r2 = t

else if t <= r3 

    r3 = t

finally we out put r3 as the answer.

class KthSmallest {
  public static void main(String[] args) {
    int[] a = new int[]{3, 0, -1, 0, 8, 7};
    System.out.println(getKthSmallest(a));
  }
  public static int getKthSmallest(int[] a) {
    int N = a.length;
    if(N < 2) return Integer.MAX_VALUE;
    int r1 = Integer.MAX_VALUE;
    int r2 = Integer.MAX_VALUE;
    int r3 = Integer.MAX_VALUE;
    //  3, 0, -1, 0, 8, 7
    //               i
    //  r1   r2    r3
    //                t
    //  -1   0      0         
    for(int i = 0; i < N; i++) {
      int t = a[i];
      if(t <= r1) {
        r3 = r2;
        r2 = r1;
        r1 = a[i];
      } else if(t <= r2) {
        r3 = r2;
        r2 = t;
      } else if(t < r3) {
        r3 = t;
      }
    }
    return r3;
  }
}

The time complexity is O(N), the space complexity is O(1).

If K is a big number such as 20, this method won't be great. We need to use a stack instead. the current value t is compared with the top element in the stack. If t is smaller, the stack pop out, then the t is added to the stack in the right position. Finally, pop out the top of the stack, which is the answer.

Three Sum Equals

Problem

Given an array of integers, find all the triplets that sum to zero. 

For example, given array {2, 1, -1, 3, 0, -2, -3, -1}, a possible output should be:

{-3,0,3},{-3,1,2},{-2,-1,3},{-2,0,2},{-1,-1,2},{-1,0,1}

Solution

brutal force approach is to find all the triplets and test if they sum to zero. We need one loop for each number, the time complexity is O(N^3).

approach 2.

We know a fast way to solve 2 sum. Given a + b = sum, we can iterate through the array, store the element value and its index into a HashMap. Later when we meet a value a, we can check the HashMap to find out if (sum - a) is in the HashMap, if yes, we pair the a's index and (sum - a)'s index to make a two sum pair. Since map put and get only cost 1, the time cost is O(N) for two sum, the extra space cost is the HashMap, which is O(N) as well.

Similarly, we can solve three sum by converting it to two sum problem.

We can iterate through the array, for each element a, we are looking for a two sum pair that sum up to (-a). In order to find that two sum pair, we can iterate through the rest of the elements, find all the two sums and pair them with a to get triplets. One problem is there could be duplicates. We can solve it by sorting the triplets, then add them into a Set in oder to remove duplicates. The time cost will be O(N^2), one N is for looping through the array, the other N is for two sum calculation. Space cost is bound by the HashMap for two sum and the Set, which is O(N).

approach 3. 

If the array is sorted, we can do better. We need 3 pointers, pointer i to the smallest element in the triplet, pointer lo = i + 1 and pointer hi = arr.length - 1 initially. 

if arr[i] + arr[lo] + a[hi] < 0, 

    we increase lo 

else if arr[i] + arr[lo] + a[hi] > 0 

    we decrease hi 

else

    we found a three sum. 

We will continue to increase lo and hi until they cross.

In this way, we can found all the three sum pairs with a for loop and a while loop, the cost will be N^2, we also need to sort the array, which cost NlogN, so the time is bounded by O(N^2). Besides a few pointers, no extra space is needed, the space cost is O(1).

-3, -2, -1, -1, 0, 1, 2, 3

            i                    

                 l                          

                                 h

                                  

import java.util.*;
class ThreeSum {
  private static int TARGET = 0;
  public static List<String> getThreeSum(int[] arr) {
    List<String> sums = new ArrayList<>();
    Arrays.sort(arr);  //3 way quick sort by jvm, O(NlogN)
    //-3, -2, -1, -1, 0, 1, 2, 3 
    //                   i
    //                      lo
    //                         hi
    //{-3,0,3},{-3,1,2},{-2,-1,3},{-2,0,2},{-1,-1,2},{-1,0,1}
    int N = arr.length;
    for(int i = 0; i < N; i++) {
      int lo = i + 1;
      int hi = N - 1;
      if(i > 0 && arr[i] == arr[i - 1]) //prevent duplicate
        continue;
      if(arr[i] > TARGET) break;
      while(lo < hi) {
        int cmp = arr[i] + arr[lo] + arr[hi];  //0 + 1 + 3 = 4
        if(cmp == TARGET) {
          sums.add(String.format("[%d, %d, %d]", arr[i], arr[lo], arr[hi]));
          while(lo < hi && arr[lo] == arr[lo + 1]) lo++; //skip duplicate
          while(lo < hi && arr[hi] == arr[hi - 1]) hi--;
          lo++;
          hi--;
        } else if(cmp < TARGET) {
          lo++;
        } else {
          hi--;
        }
      }
    }
    return sums;
  }
 
  public static void main(String...args) {
    int[] arr = new int[] {2, 1, -1, 3, 0, -2, -3, -1};
    List<String> sums = getThreeSum(arr);
    sums.forEach(System.out::println);
  }
}

The time cost is O(N^2), the space cost is O(1).

Selection Sort

Back>

Selection sort selects the minimum by scanning n elements, taking n-1 comparisons, and then swapping it into the first position. Finding the next lowest element requires scanning the remaining n-1 elements and so on.

SelectionSort.java

0

1

2

3

4

5

6

7

8

9

function selectionSort(a) {
  var N = a.length;
  for (var i = 0; i < N; i++) {
     var min = i;
     for (var j = i+1; j < N; j++) {
       if (a[j] < a[min]) min = j;
     }
     exch(a, i, min);
  } 
} 

Selection sort is the simplest sorting algorithm to understand. However, in order to sort, it needs to do lots of comparisons: (n-1) + (n-2) + (n-3) ...+ 1 = n x (n-1)/2. When n is very large, the amount of computations are roughly proportional to n square. So in the terms of computation complexity, it is the most complex algorithm, with complexity of O(n^2).


Fun fact:

Embedded system such as FPGA can customize hardware for specific task. Fine tune the hardware by the character of less swap is needed, the FPGA can allocate faster computation units to comparison operation, but slower computation units to swap operation, in order to achieve the best cost/effect of the hardware resource.

FPGA

hardware programing code

Next>