package filesystem;
import java.util.ArrayList;
import java.util.Date;
public class FileSystem {
    public class file {
        private String name;
        private long size;
        private Date timeStamp;
        private file currentDir;
        private file parentDir;
        // a directory is also a file containing reference to other files
        private boolean isDirectory;
        public ArrayList<file> subfiles;
        // Advanced class members if required
        private boolean[] permissions;
        private String owner;
        private String group;
           
        public file(String name, file currentDir, boolean isDir) {
            this.name = name;
            this.currentDir = currentDir;
            this.timeStamp = new Date();
            this.isDirectory = isDir;
            this.size = 0; // initial size
            this.parentDir = currentDir.getParentDirectory();
            if (isDir == true)
                this.subfiles = new ArrayList<file>();
        }
        
        public void updateTimeStamp() {
            this.timeStamp = new Date();
        }
        
        public file getParentDirectory() {
            return this.parentDir;
        }
        
        public void rename(String name) {
            this.name = name;
        }
    
    }
    
    private file root; // root folder
    public FileSystem() {
        // every file system should have a root folder
        this.root = new file("root", null, true);
    }
    
    public void createFile(String name, file curDir, boolean isDir) {
        file f = new file(name, curDir, isDir);
        curDir.subfiles.add(f);
    }
}

public List<Point> closestNeighbors(Point[] points, Point center) {
	Comparator<Point> comparator = new Comparator<Point>() {
		public int compare(Point left, Point right) {
			return distance(right, center) - distance(left, center);
		}
	};
	PriorityQueue<Point> queue = new PriorityQueue<Point>(comparator);
	for (Point p : points) {
		if (queue.size() < k) {
			queue.offer(p);
		} else {
			if (distance(p, center) < queue.peek()) {
				queue.poll();
				queue.offer(p);
			}
		}
	}
	List<Point> res = new ArrayList<Point>();
	while (!queue.isEmpty()) {
		res.offer(queue.poll());
	}
	return res;
}
private int distance(Point a, Point b) {
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        Stack<Integer> stack = new Stack<Integer>();
        int max = Integer.MIN_VALUE;
        stack.push(0);
        for (int i = 1; i < heights.length; ++i) {
            int current = heights[i];
            while (!stack.isEmpty() && current < heights[stack.peek()]) {
                int bar = heights[stack.pop()];
                int left = stack.isEmpty()? -1 : stack.peek();
                max = Math.max(bar * (i - left - 1), max);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int bar = heights[stack.pop()];
            while (!stack.isEmpty() && heights[stack.peek()] == bar) {
                stack.pop();
            }
            int left = stack.isEmpty() ? -1 : stack.peek();
            max = Math.max(max, bar * (heights.length - left - 1));
        }
        return max;
    }
}

public class Solution {
    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int res = 0;
        Stack<Integer> stack = new Stack<Integer>();
        int[] h = Arrays.copyOf(heights, heights.length + 1); // padding zero at the end
        for (int i = 0; i < h.length; ++i) {
            int bar = h[i];
            while (!stack.empty() && bar < h[stack.peek()]) {
                int last = h[stack.pop()];
                // calculate the width
                int width = stack.empty() ? i : i - stack.peek() - 1;
                res = Math.max(res, width * last);
            }
            stack.push(i);
        }
        return res;
    }
}

public bool isAlive(int[][] board, int i, int j) {
	// Mark visited nodes as Integer.MAX_VALUE;
	if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == -1 || board[i][j] == Integer.MAX_VALUE) {
		return false;
	}	
	if (board[i][j] == 0) {
		return true;
	}
	board[i][j] = Integer.MAX_VALUE;
	return isAlive(board, i + 1, j) || isAlive(board, i - 1, j) || isAlive(board, i, j + 1) || isAlive(board, i, j - 1);
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int[] findFrequentTreeSum(TreeNode root) {
        if (root == null) {
            return new int[0];
        }
        
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        helper(root, map);
        
        // Sort map entry based on the frequency
        Comparator<Map.Entry<Integer, Integer>> comparator = new Comparator<Map.Entry<Integer, Integer>>() {
            public int compare(Map.Entry<Integer, Integer> left, Map.Entry<Integer, Integer> right) {
                return right.getValue().compareTo(left.getValue());
            }
        };
        List<Map.Entry<Integer, Integer>> res = new ArrayList<Map.Entry<Integer, Integer>>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            res.add(entry);
        }
        
        res.sort(comparator);   // Sort by frequency in decreasing order
        int maxFreq = res.get(0).getValue();
        List<Integer> temp = new ArrayList<Integer>();
        for (int i = 0; i < res.size(); ++i) {
             if (res.get(i).getValue() == maxFreq) {
                 temp.add(res.get(i).getKey());
             }
        }
        
        int[] resArray = new int[temp.size()];
        for (int i = 0; i < temp.size(); ++i) {
            resArray[i] = temp.get(i);
        }
        
        return resArray;
    }
    
    private int helper(TreeNode root, Map<Integer, Integer> freqMap) {
        if (root == null) {
            return 0;
        }
        
        int left = helper(root.left, freqMap);
        int right = helper(root.right, freqMap);
        
        int sum = left + right + root.val;
        freqMap.put(sum, freqMap.getOrDefault(sum, 0) + 1);
        return sum;
    }
}

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        
        if (nums == null || nums.length == 0) {
            return new int[0];
        }
        
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(Collections.reverseOrder());
        
        int[] res = new int[nums.length - k + 1];
        
        for (int i = 0; i < nums.length; ++i) {
            if (queue.size() >= k) {
                queue.remove(nums[i - k]);
            }
            queue.offer(nums[i]);
            if (i  + 1 >= k) {
                res[i - k + 1] = queue.peek();
            }
        }
        
        return res;
    }
}

public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) {
            return new int[0];   
        }
        
        LinkedList<Integer> deque = new LinkedList<Integer>();  
        int[] res = new int[nums.length - k + 1];
        for (int i = 0; i < nums.length; ++i) {
            if (!deque.isEmpty() && deque.peekFirst() == i - k) {
                deque.removeFirst();
            }
            
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.removeLast();
            }
            
            deque.offer(i);
            if (i + 1 >= k) {
                res[i - k + 1] = nums[deque.peekFirst()];
            }
        }
        
        return res;
    }
}

public class Solution {
    public int maxRotateFunction(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int f = 0;
        int sum = 0;
        for (int i = 0; i < A.length; ++i) {
            f += i * A[i];
            sum += A[i];
        }
        
        int res = f; // f(0)
        for (int i = 1; i < A.length; ++i) {
            f = f + sum - A.length * A[A.length - i];
            res = Math.max(res, f);
        }
        
        return res;
        
    }
}