Permutations

Given a collection of distinct numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:

[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

Algorithm:

See Combinations. Simply without rule 2. But the IO settings is a little bit different than Combination, which give you n numbers from 1~n and k buckets. In this problem, it gives you a set of predefined numbers. So instead of start with the first number, you start with nums[0]. And you need an additional array to mark the numbers that already show up.

Solution:

class Solution {
  
    void DFS(int[] visited, int[] nums, List<Integer> ans, List<List<Integer>> res)
    {
      if( ans.size() == nums.length ){
        List<Integer> tmp = new ArrayList<Integer>(ans);
        res.add(tmp);
        return;
      }
      for(int i = 0; i < nums.length; i++){
        if( visited[i] == 0 ){
          visited[i] = 1;
          ans.add(nums[i]);
          DFS(visited, nums, ans, res);
          ans.remove(ans.size()-1);
          visited[i] = 0;
        }
      }
    }
    
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> answer = new ArrayList<Integer>();
        int[] visited = new int[nums.length]; 
        
        DFS(visited, nums, answer, result);
      
        return result;
    }
}

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Algorithm:

Imagine you have n cards on your hand and each card has a unique number between 1~n. There are k buckets in front of you. You need to drop your cards into the buckets to come up with a combination.

There's only one rule to follow:

Each time you step in front of the ith bucket, you have to increase the number to drop in from last time.

For example, you drop in 1 in the first bucket, next time you step in front of the first bucket, you have to drop in 2.

Say n = 3, k = 2

          

i = 1 : [ 1 ] [ ]      Drop one in the first bucket

i = 2 : [ 1 ] [ 2 ]   => one combination (1, 2)

i = 2 : [ 1 ] [ ]     When the bucket is full, retrieve the card back to your hand

i = 2 : [ 1 ] [ 3 ]   Because you drop in 2 last time, so you drop in 3  => 2nd combination (1, 3)

i = 2 : [ 1 ] [ ]

i = 1 : [ ] [ ]         You can't drop in 4, so step to the first bucket(rest count on i = 2),
                          and retrieve 1 back to your hand

i = 1 : [ 2 ] [ ]      Because you drop in 1 last time at i = 1, so you drop in 2

i = 2 : [ 2 ] [ 1 ]   Since the count were reset, drop in 1 => (2, 1)

i = 2 : [ 2 ] [ ]

i = 2 : [ 2 ] [ 3 ]   Since 2 is not available, drop in 3 => (2, 3)

i = 2 : [ 2 ] [ ]

i = 1 : [ ] [ ]         Reset count for i = 2

i = 1 : [ 3 ] [ 1 ]   => (3, 1)

i = 2 : [ 3 ] [ ]     

i = 2 : [ 3 ] [ 2 ]   => (3, 2)

We notice that the result is actually the permutation of 3 out of 2 elements. So the combination has to divide by k! which is 2 in this case. To achieve the requirement, we have to add one more rule to the algorithm: The number in the bucket has to be bigger than the one in the previous bucket.

Hence, (3, 1), (3, 2) and (2, 1) is not valid

The mathematical calculation for only one rule is Cn_k * k! = n! / (n-k)! = 3! / 1! = 6

The mathematical calculation for two rules is Cn_k = n! / ((n-k)! * k!) = 3! / (2! * 1!) = 3

Solution:

class Solution {
  
    void DFS(int n, int k, int step, List<Integer> ans, List<List<Integer>> res){
      if( ans.size() == k ){
        ArrayList<Integer> temp = new ArrayList<Integer>(ans);
        res.add(temp);
        return;
      }
  
      // Start with step, which implies the 2nd rule
      // i.e. You will get (1,2) but not (2,1)
      // If you want to get all the permutations, you start with i = 1
      for(int i=step; i <= n; i++){
          ans.add(i);
          DFS(n, k, i+1, ans, res);
          ans.remove(ans.size()-1);
      }
      
    }
  
    public List<List<Integer>> combine(int n, int k) {
      List<List<Integer>> result = new ArrayList<List<Integer>>();
      List<Integer> answer = new ArrayList<Integer>();
      
      DFS(n, k, 1, answer, result);
      
      return result;
        
    }
}

Performance:

Maximum movies watched

Alex and Tom share a common passion for movies, but unfortunately they do not really like each other. A movie festival is taking place in another town, and both of them want to participate in it. The problem is the neither of them is willing to meet the other during the event.

After some not very pleasant negotiations, they agree that the fairest way to fulfill both goals is to pick two intervals of time so as to maximize the total number of movies that they can both see on their own. Keeping in mind that Alex and Tom each want to spend several days in a row at the festival(as the town in which the event is taking place is not close by, so they do not want to travel there more than once), help them count the maximal number of movies that can be seen by both of them independently.

int getMaxMoviesWatched(int[] movies, int K, int L)

movies is an array of size N which specifies the number of movies on each day of the festival
K is the number of days for Alex
L is the number of days for Tom

Assume N is an integer within the range of [2,600]
K and L are integers within the range [1,N-1]
Each element of array movies is an integer within the range [1,500]

return the maximal number of movies that can be seen by both of them or -1 if a solution is not possible.

Examples:

movies = [6, 1, 4, 6, 3, 2, 7, 4], K = 3, L = 2

Alex can participate 4+6+3 = 13 movies
Tom                          7+4 = 11 movies

Return 13+11=24

movies = [10, 19, 15], K=2, L=2

Return -1

My Solution: (Might be wrong, please advice) 

  static int getMaxMoviesWatched(int[] movies, int K, int L){
    int length = movies.length;
    if ( length < K+L )
      return -1;

    int maxK = 0;
    int indK = 0;
    for(int i = 0; i <= length-K; i++){
      int value = 0;
      for(int j = i; j < K+i; j++)
        value += movies[j];

      if ( value > maxK ){
        maxK = value;
        indK = i;
      }
    }

    int maxL = 0;
    for(int i = 0; i <= length-L; i++){
      int value = 0;
      if( i == indK )
        i += K;

      for(int j = i; j < L+i; j++)
        value += movies[j];

      if ( value > maxL ){
        maxL = value;
      }
    }

    return maxK + maxL;

  }

Maximum squared distance

Four integers A, B, C, D are given. The integers can be used to describe two points on a plane by assigning their values to the coordinates of the points. Each integer has to be assigned to exactly one coordinate. Your task is to assign the integers A, B, C and D to the coordinates of two points in such a way as to maximize the squared distance between those points.

int getMaxDistanceSquare(int A, int B, int C, int D)

Assume that:

A, B, C and D are integers within the range [-5000, 5000]

For example, let's consider the following values:
A = 1
B = 1
C = 2
D = 3

We have:
(1, 1) <=> (2, 3)  or (3, 2) squared distance = 5 or 5      MAX = 5
(1, 2) <=> (1, 3)      (3, 1)                                1     5
(1, 3) <=> (1, 2)      (2, 1)                                1     5

For Example,

A = 2
B = 4
C = 2
D = 4

We have:
(2, 4) <=> (2, 4) or (4, 2) squared distance = 0 or 8      MAX = 8
(2, 2) <=> (4, 4)                                              8
(2, 4) <=> (4, 2) or (2, 4)                                8     0

For Example,
A = 1
B = 2
C = 3
D = 4

We have:
(1, 2) <=> (3, 4) or (4, 3) squared distance = 8 or 10    MAX = 10
(1, 3) <=> (2, 4) or (4, 2)                                1     10
(1, 4) <=> (2, 3) or (3, 2)                                1      8


My Solution: (Might be wrong, please advice) 

  static int getMaxDistanceSquare(int A, int B, int C, int D){
    int max = -1; 
    int[] dist = new int[3];
    dist[0] = (A-B)*(A-B) + (C-D)*(C-D); 
    dist[1] = (A-C)*(A-C) + (B-D)*(B-D);
    dist[2] = (A-D)*(A-D) + (B-C)*(B-C);

    for(int i = 0; i < 2; i++)
      max = dist[i] > dist[i+1] ? dist[i] : dist[i+1];

    return max;
  }