Russian doll envelopes


  • 5
    Y

    You have a set of envelopes of different widths and heights. One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
    What is the maximum number of envelopes can you Russian doll? (put one inside other)


  • 1

    The first glance at this problem seems that it is not that easy. After diving into it, I found that this problem is the "Longest Common SubArray" problem.
    Let me give some analysis:
    There are two conditions to ensure that a smaller envelope can be wrapped into another: smaller width and smaller height. So let's first satisfy one condition:

    1. Sort the envelopes with their width to get Array1: a1, a2, a3, a4, a5, a6, a7, a8 with O(n*logn)
    2. Sort the envelopes with their height to get Array2: b1, b2, b3, b4, b5, b6, b7, b8 with O(n*logn)

    Any list that satisfy the "Russian doll" must be the subarray of both Array1 and Array2. So our task here is to find the Longest Common SubArray of Array1 and Array2 which can be accomplished with DP in O(n*n)

    So the total time complexity is O(n*n).


  • 1

    @xidui
    Another approach I can think of is, sort the lengths (for same lengths, decreasing order widths).
    Discard all duplicate lengths, by picking length having max width among them.
    Apply longest increasing subsequence to the widths (binary search approach).
    Total complexity is O(n logn).


  • 0
    public int envelopes(int[][] env) {
        Arrays.sort(env, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] < o2[0])
                    return -1;
                if (o1[0] > o2[0])
                    return 1;
                if (o1[1] > o2[1])
                    return -1;
                if (o1[1] < o2[1])
                    return 1;
                return 0;
            }
        });
    
        List<Integer> widths = new ArrayList<Integer>();
        List<Integer> res = new ArrayList<Integer>();
        widths.add(env[0][1]);
        for(int i = 1; i < env.length; i++) {
            if(env[i-1][0] != env[i][0]) {
                widths.add(env[i][1]);
            }
        }
    
        for(int i = 0; i < widths.size(); i++) {
            int idx = binarySearch(res, widths.get(i));
            if(idx < res.size()) {
                res.set(idx, widths.get(i));
            }else {
                res.add(widths.get(i));
            }
            System.out.println(res);
        }
    return res.size();
    }
    
    public int binarySearch(List<Integer> result, int key) {
        int low = 0, high = result.size()-1;
        while(low <= high) {
            int mid = low + (high - low) / 2;
            if(result.get(mid) == key) {
                if(mid == 0) return mid; // last element so return
                if(result.get(mid-1) == key) {
                    high = mid - 1; // moving left
                }else {
                    return mid;
                }
            }else if (result.get(mid) < key) {
                low = mid + 1;
            }else {
                high = mid - 1;
            }
        }
        if(low == result.size()-1 && result.get(low) < key) {
            return low + 1; // if key not found, and low points to last element.
        }
        return low;
    }

  • 0

    The idea is to sort the envelopes by their sizes (width * height) and then use DFS + dp to find the max amount of envelopes can be fit into one. Thus, dp[i] servers as the memory to store the maximum envelopes from index i to the last one. If dp[i] == 0, it means that i has not been visited yet. Each index i only needs to be visited once.
    One thing can be improved in the following code is that a binary search can be used to find the variable "next" , the next larger envelope, based on current envelope's size. i.e. if current one has width = 2 and height = 3, the next envelope should have at least the size of (2+1)*(3+1) = 12. That's one of the reasons I sort the given envelopes by size.
    The following are the code:

    public static class Env implements Comparable<Env> {
    	int w;
    	int h;
    	long area;
    	public Env(int wd, int ht) {
    		w = wd;
    		h = ht;
    		area = (long) w * h;
    	}
    	public int compareTo(Env e1) {
    		int comp = Long.compare(area, e1.area);
    		if (comp == 0) comp = Integer.compare(w, e1.w);
    		if (comp == 0) comp = Integer.compare(h, e1.h);
    		return comp;
    	}
    	boolean canFitIn(Env e1) {
    		return ((e1.w > w) && (e1.h > h));
    	}
    }
    
    void dfs(int i, int[] dp, Env[] list) {
    	int len = list.length;
    	if (dp[i] == 0) {
    		int max = 0;
    		int next = i+1;
    		while ( next < len )  {
    			if ( list[i].canFitIn(list[next]) ) {
    				if ( dp[next] == 0 ) dfs(next, dp, list);
    				max = Math.max( max, dp[next]);
    			}
    			next++;
    		}
    		dp[i] = max+1;
    	}
    }
    
    int findMaxEnv(Env[] envs) {
    	if (envs == null || envs.length == 0) return 0;
    	int ret = 0;
    	int len = envs.length;
    	int[] dp = new int[len];
    	Arrays.sort(envs);
    	for (int i=0; i < len; i++) {
    		dfs(i, dp, envs);
    		ret = Math.max(ret, dp[i]);
    	}
    	return ret;
    }

  • 0

    I think that we have to sort by width, then to apply longest increasing subsequence by heights. I wonder whether it is the same approach like this presented by @andyreadsall


  • 1
    G

    @andyreadsall "Discard all duplicate lengths, by picking length having max width among them." Seems not right, example:
    width: 1 2 3 3 4 5 5 6 7
    length: 2 3 4 5 5 5 6 7 8
    we have three length=5, and the longest width sequence should be 1234567
    However if we ignore width 3,4 with length 5, we have 123567


  • 0

    @GoGoDong .. Envelope can be added one inside the other only if both length and width are smaller. So you've to pick only one, and the best choice is to pick the one with max width.

    EDIT: My bad; I think you're right. : Good counter example!
    My original solution will discard Envelop L:5W:4, because it selects L:5W:5, which is wrong. Final set of envelopes must be :
    [2,1],[3,2],[4,3],[5,4],[6,5],[7,6],[8,7] but my original solution would be this : [2,1],[3,2],[4,3],[5,5],[7,6],[8,7]

    Changed the code to this: But it's O(n^2)

    public int envelopes(int[][] env) {
        Arrays.sort(env, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] < o2[0])
                    return -1;
                if (o1[0] > o2[0])
                    return 1;
                if (o1[1] > o2[1])
                    return -1;
                if (o1[1] < o2[1])
                    return 1;
                return 0;
            }
        });
    
        int[] dp = new int[env.length];
        int result = 0;
        Arrays.fill(dp, 1);
        for(int i = 0; i < env.length; i++) {
            for(int j = 0; j < i; j++) {
                if(env[i][1] > env[j][1] && env[i][0] > env[j][0]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
                result = Math.max(dp[i], result);
            }
        }
        return result;
    }

  • 0
    G

    @andyreadsall
    Thanks for sharing the code!
    Can we still achieve O(nlgn) by improving the binary search?
    Since your code already makes decreasing order of widths on even lengths (the above example, L5 W5, L5 W4, L5 W3), so when we are currently at L4 W3, we want to see if there is L5 with at least W4, but as small W as possible. Here binary search can work again.


  • 0

    @GoGoDong Thumbs up for this great counter example!


  • 2

    @GoGoDong

    I'm not sure if we can do binarySearch.
    For example, after sorting, if envelopes look
    [2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380],
    and if we go by binary search it will look something like,
    [2,100],[3,200],[4,300],[5,400]. But [5,400] is wrong choice since the next elements are [6,370],[6,360],[7,380] etc, and we already lost [5,250]

    In this case, answer should have been [2,100],[3,200],[5,250],[6,360],[7,380]


  • 0

    @andyreadsall
    So, in the case you provided, if we sort them by size (w*h), the binary search might work since after [4,300] the search algorithm will pick [5,250] first instead of [5,400]. :)
    As a result, the search condition will be to find the minimum envelope with w and h greater the last one.


  • 0

    @yubad2000 Areas can be same for different dimensions. 1x20, 2x10, 4x5, 5x4, 10x2, 20x1 .. all have same areas.


  • 0
    This post is deleted!

  • 0

    Not sure about whether my improved solution is n*log(n).
    The improvements are:

    1. Using binary search to find the next starting envelope instead of stepping one by one.
    2. Early termination when the number of rest envelopes is less than current maximum.
    3. Implementing backtracking to show the result of all chosen envelopes.

    Here is the code:

    public class RussianDollEnvelopes {
    
    	public static class Env implements Comparable<Env> {
    		int w;
    		int h;
    		long area;
    		public Env(int wd, int ht) {
    			w = wd;
    			h = ht;
    			area = (long) w * h;
    		}
    		public int compareTo(Env e1) {
    			int comp = Long.compare(area, e1.area);
    			if (comp == 0) comp = Integer.compare(w, e1.w);
    			if (comp == 0) comp = Integer.compare(h, e1.h);
    			return comp;
    		}
    		boolean canFitIn(Env e1) {
    			return ((e1.w > w) && (e1.h > h));
    		}
    		public String toString() {
    			return "["+w+","+h+"] ";
    		}
    	}
    	/* Instead of stepping one by one, binary search is used to 
    	 * find the next starting envelope which can fit the current one 
    	 */
    	int findNext(int i, Env[] list, int len) {
    		if (i>=len) return i;
    		long min_area = (long)(list[i].w+1) * (long)(list[i].h+1);
    		int s = i+1;
    		int e = len;
    		while (s < e) {
    			int mid = s+(e-s)/2;
    			Env m = list[mid];
    			if ( (m.area < min_area) || (! list[i].canFitIn(m)) ) s = mid+1;
    			else e = mid;
    		}
    		return s;
    	}
    	void dfs(int i, int[] dp, Env[] list, String[] paths, String path) {
    		int len = list.length;
    		String ret = list[i].toString();
    		int max_idx = -1;
    		if (dp[i] == 0) {
    			int max = 0;
    			int next = findNext(i, list, len);
    			//while ( next < len  )  {
    			while (  len - next > max  )  { // early termination
    				if ( list[i].canFitIn(list[next]) ) {
    					if ( dp[next] == 0 ) {
    						dfs(next, dp, list, paths, ret);
    					}
    					if (dp[next] > max) {
    						max = dp[next];
    						max_idx = next;
    					}
    				}
    				next++;
    			}
    			dp[i] = max+1;
    			ret = max_idx < 0 ? ret : ret + paths[max_idx]; 
    			paths[i] = new String(ret);
    		}
    	}
    	
    	int findMaxEnv(Env[] envs) {
    		if (envs == null || envs.length == 0) return 0;
    		int len = envs.length;
    		int[] dp = new int[len];
    		String[] paths = new String[len];
    		int max_idx = -1;
    		Arrays.sort(envs);
    		for (int i=0; i < len; i++) {
    			dfs(i, dp, envs, paths, "");
    			if ( max_idx < 0 || dp[i] > dp[max_idx]) {
    				max_idx = i;
    			}
    		}
    		System.out.println(paths[max_idx]);
    		return dp[max_idx];
    	}
    
    }
    

  • 1

    Here is my implementation.
    First sort by width, if there are ties sort by height in descending way. For example :
    1 2 3 4 5 5 6 7
    2 3 4 5 6 5 7 8
    Then find the longest increasing subsequence by height, following the rule that when there is an envelope with width already in the current LIS, we don't add it , but put it in a place in current longest sequence, where all envelopes before it have heights which are strictly less its height. I made some tests. Time complexity nlog(n).
    Example :
    1 3 6 6 8 9
    3 5 7 8 4 5

    1. lis = [3]
    2. 5 > 3 => lis = [3,5]
    3. 7 > 5 => lis = [3,5,7]
    4. 8 > 7 but 6 is already width of an envelope in lis , move 8 to its place => lis [3,5, 8]
    5. 4 < 7 move to its place => [3,4,8]
    6. 5 < 8 move => [3,4,5]
      max number of envelopes- size of lis which is 3
    int findMaxNumOfEnvelopes(List<Envelope> envelopes) {			
    			Collections.sort(envelopes, new Comparator<Envelope>() {
    
    				@Override
    				public int compare(Envelope a, Envelope b) {
    					if (a.width == b.width) {
    						return b.height - a.height;
    					}
    					return a.width - b.width;
    				}				
    			});	
    			
    			List<Integer> lis = new ArrayList<Integer>();			
    			int lastVal = envelopes.get(0).height;			
    			int index = 0;
    			int lastIndex = -1;
    			
    			while (index < envelopes.size()) {    
    				
    				if (index == 0 || (envelopes.get(index).height > lastVal && envelopes.get(lastIndex).width != envelopes.get(index).width)) {						
    				    lastIndex++;
    				    lis.add(index);
    				    lastVal = envelopes.get(index).height;
    				}
    				else if (envelopes.get(index).height  <  lastVal) {									
    					int l = 0;
    					int r  = lis.size() - 1;
    					int val = 0;
    					while  (l  <=  r) {
    						int mid = (l + r)/2;
    						int midVal = envelopes.get(lis.get(mid)).height;
    						if  (envelopes.get(index).height  ==  midVal)  {						
    							val = mid;
    							break;
    						} else if (midVal  >  envelopes.get(index).height) 
    							r--;						
    						else
    							l++;
    					}
    					if  (l  >  r)  {											
    						val = l;
    					}	
    					lis.set(val, index);
    					if (lis.size() - 1  ==  val)
    						lastVal =  envelopes.get(index).height;
    				}				
    				index++;
    			}
    			return lis.size();
    		}

  • 0

    @elmirap
    Will this work for this example ? [2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]


  • 0

    @andyreadsall I tried it, it returns 5


  • 0
    This post is deleted!

  • 0

    it looks good


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.