Leetcode: Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges.

For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].

Runtime Analysis:

Runtime: O(n)

Algorithmic Approach:

This is an easy question. Since the ranges are all continuous integers, we just need traverse the array and compare each element with its previous, if they are not consecutive, the current number belongs to a new range. In my code, the start and end of the current range is maintained. Don't forget to consider a single number range and the slightly different output format required in this question.

Java Code:

 public class Solution {
    public List<String> summaryRanges(int[] nums) {
        
        int start = 0, end = 0;
        List<String> toRet = new ArrayList<String>();
        String str = "";
        
        if(nums.length == 0)
            return toRet;
        
        for(int i = 0; i < nums.length - 1; i++){
            
            // if consecutive
            if(nums[i] + 1 == nums[i + 1]){
                end++;
                
                // if the start, adds the string
                if(i == start){
                    str = nums[i] + "";
                }
            }
            
            // if not consecutive
            else{
                if(start != end){
                    str += "->" + nums[i];
                }
                else{
                    str = nums[i] + "";    
                }
                
                toRet.add(str);
                start = i+1;
                end = i+1;
            }
        }
        
        // covers the last element
        if(start == end){
            toRet.add(nums[end]+"");
        }
        else{
            str += "->" + nums[end];
            toRet.add(str);
        }
        
        return toRet;
    
    }
}

Leetcode: Merge Intervals

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].

Runtime Analysis:

Since we are given a set of n intervals, to combine them, we need to at least traverse each interval once, thus taking O(n) time where n is the number of intervals. The lower bound of our algorithm must at least be (Omega) Ω(n). 
  
One possible approach would be to sort the list of intervals by:

1. Starting Value
2. Ending Value

In this case, you would get a list of sorted intervals by their starting values. To sort the intervals, you could: 

1. Create your own interval class implementing the Comparable Interface, and providing the appropriate compareTo() method
2. Create a custom Comparator Class implementing the Compare() method. 

Then, simple call sort() on the list (providing your Comparator if you chose (2)). 

One approach could be to visit every possible consecutive pair of intervals in the list and try to combine the pair if they overlap. In a list with N intervals, we have N-1 possible pairs to combine. However, after you traversed each consecutive pair, if you combined at least 1 pair during that loop, it is possible that the new interval made could also overlap with its neighbor, so you would have to continue to loop N-2 times. In the worse case, all intervals overlap with each other or and thus taking O(n2) time.

A quadratic runtime, unfortunately, is not fast enough in this case. There is a better O(n) approach. 

Runtime: O(n)




Algorithmic Approach:

Normally, without sorting the intervals by start, we would have 4 basic cases of intersection:

However, after sorting, we are left with Diagrams (2) and (4) on the right hand side. In both cases, we can apply the following algorithm:

Given interval A, B intersect, our new interval is: [A_start, Max(A_end, B_end)]

The final step would be to determine if our intervals did overlap. 

Given intervals P and D, we know that the intervals intersect if fd < kp. This condition tells us if we need to merge our intervals or not.

Java Code: 

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
 
class IntervalComparator implements Comparator<Interval>{
    public int compare(Interval a, Interval b){
        if(a.start < b.start){
            return -1;
        }else if(a.start > b.start){
            return 1;
        }else{
            if(a.end < b.end){
                return -1;
            }else if(a.end > b.end){
                return 1;
            }else{
                return 0;
            }
        }
    }
     
 }
 
public class Solution {
    
    public List<Interval> merge(List<Interval> intervals) {
        
        List<Interval> list = new ArrayList<Interval>();
        
        if(intervals.size() == 0)
            return list;
        
        Collections.sort(intervals, new IntervalComparator());
        
        list.add(intervals.get(0));
        
        for(int i = 1; i < intervals.size(); i++){
            if(intervals.get(i).start <= list.get(list.size()-1).end){
                list.get(list.size()-1).end = Math.max(intervals.get(i).end, list.get(list.size()-1).end);
            }else{
                list.add(intervals.get(i));
            }
        }
        return list;
    }
}

Priyanka and Toys

Difficulty: Easy

Little Priyanka visited a kids' shop. There are N toys and their weight is represented by an array W=[w1,w2,…,wN]. Each toy costs 1 unit, and if she buys a toy with weight w′, then she can get all other toys whose weight lies between [w′,w′+4](both inclusive) free of cost.

Input Format

The first line contains an integer N i.e. number of toys.
Next line will contain N integers, w1,w2,…,wN, representing the weight array.

Output Format

Minimum units with which Priyanka could buy all of toys.

Constraints
1≤N≤105
0≤wi≤104,where i∈[1,N]

Sample Input

5
1 2 3 17 10

Sample Output

3

Explanation

She buys 1st toy with weight 1 for 1unit and gets 2nd and 3rd toy for free since their weight lies between [1,5]. And she has to buy last two toys separately

Runtime Analysis:

Given the following constraints:

1≤N≤105
0≤wi≤104,where i∈[1,N]

We know that in the worst case, we have to process 105 elements (Just reading in the input). The average processor (usually assumed to be 2GHz) can do 2 x 109  possible operations per second. However each line of code often takes more than 1 operation to perform, so we often estimate 2 x 108 operations per second (off by factor of 10), which means that, for a linear solution, we can execute our code within 1 second and is most likely a viable solution. However, anything more than linear will likely cause a timeout. O(n2) will take 1010  which will take about 50 seconds to compute. Typically,  Hacker rank contests have a 4 second time out for Java solutions, which means we need to write a O(n) solution.

Runtime: O(n)




Algorithmic Approach:

This question is a great beginning to learning the Greedy Algorithm. In this case, a simple Greedy Approach will suffice and solve the problem. Since Priyanka gets toys of the price [w, w+4] for free, we sort the array and traverse each element at a time. During each iteration, we keep track of the last element we "purchased" (curr) and if our current value is greater than curr + 4 (we need to "purchase" a new element), then we add to our count and update the last "purchased" value. 




Java Code: 

import java.io.*;
import java.util.*;

public class Solution{
 

 public static void main(String []args){
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
  int [] arr = new int[n];

  for(int i = 0; i < n; i ++){
   arr[i] = sc.nextInt();
  }

  Arrays.sort(arr);

  int count = 1;
  int currVal = arr[0];

  for(int i = 0; i < n; i++){
   if(arr[i] > currVal + 4){
    currVal = arr[i];
    count++;
   }
  }

  System.out.println(count);

 }
}