[CSE] 10.20

I saw these questions in other places and think it may be worth a try. 
Question 1:
 
Given a finite set of unique numbers, find all the runs in the set. 
Runs are 1 or more consecutive numbers.
That is, given {1,59,12,43,4,58,5,13,46,3,6}, 
the output should be: {1}, {3,4,5,6}, {12,13}, {43}, {46},{58,59}.
Note that the size of the set may be very large.
 
If you think it's too easy, you can take a look at the discussion here: 
http://ayende.com/blog/163394/new-interview-question
Or you may want to think a little bit before clicking it.
 
Question 2:
 
You're given a modified text editor and there are only three operations
you can take: select all, copy and paste. Initially there's only one letter 
in the editable area. If you can take only N operations, compute the largest
number of letters you can get finally.
 
The input is N and output should be the largest number of letters.

[Solution1].java

/**
 * used Map to do it in a TC O(n), SC O(n) way,
 * could optimize SC to O(m), m is the number of consecutive numbers with same idea.
 */

public class Solution{
    public ArrayList<ArrayList<Integer>> finRuns(int[] input){
        if(input == null || input.length == 0) return null;
        ArrayList<ArrayList<Integer>> out = new ArrayList<>();
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        HashSet<Integer> begins = new HashSet<>();
        for(int i = 0; i < input.length; i++){
            int thisNumber = input[i];
            if(map.containsKey(thisNumber)) continue;
            else{
                if(map.containsKey(thisNumber - 1) && map.containsKey(thisNumber + 1)){
                    ArrayList<Integer> groupLeft = map.get(thisNumber - 1);
                    ArrayList<Integer> groupRight = map.get(thisNumber + 1);
                    groupLeft.addAll(groupRight);
                    groupLeft.add(thisNumber);
                    groupRight = groupLeft;
                    map.put(thisNumber, groupLeft);
                }
                else if(map.containsKey(thisNumber - 1)){
                    ArrayList<Integer> groupLeft = map.get(thisNumber - 1);
                    groupLeft.add(thisNumber);
                    map.put(thisNumber, groupLeft);
                }
                else if(map.containsKey(thisNumber + 1)){
                    ArrayList<Integer> groupRight = map.get(thisNumber + 1);
                    groupRight.add(thisNumber);
                    map.put(thisNumber, groupRight);
                    begins.remove(thisNumber + 1);
                    begins.add(thisNumber);
                }
                else{
                    ArrayList<Integer> group = new ArrayList<>();
                    group.add(thisNumber);
                    map.put(thisNumber, group);
                    begins.add(thisNumber);
                }
            }
        }
        for(Integer i: begins){
            out.add(map.get(i));
        }
        return out;
    }
}

[Solution2].java

/**
 *  used some triks for optimize, but basically still O(n^2)... Any better idea?
 */

public class Solution{
    public int getLargestOutput(int N){
        int[] max = new int[1];
        getLargestOutput(N, 0, 1, max);
        return max[0];
    }
    
    public void getLargestOutput(int N, int memory, int lastNumber, int[] max){
        // If step number smaller or equale to 2, then it's not worth to select and copy, just paste
        if(N <= 2){
            lastNumber += N * memory;
            if(lastNumber > max[0]) max[0] = lastNumber;
        }
        /**
         * We could cost 3 steps to "select", "copy" and "paste" in a series,
         * as there is no reason to "select" or "copy" alone.
         * 
         * Or we could cost 1 step to only "paste".
         */
        else{
            getLargestOutput(N - 1, memory, lastNumber + memory, max);
            getLargestOutput(N - 3, lastNumber, lastNumber * 2, max);
        }
    }
}

I dont think your solutition in Q1 is O(n).

line 19. addAll() actually is a operation of O(n).