idiotleon

• Pre Sum (hash map)

  • 1. Two Sum
  • 15. 3Sum
  • 18. 4Sum
  • 410. Split Array Largest Sum
  • 560. Subarray Sum Equals K

• Calculation

idiotleon

• Pre Sum (hash map)

  • 1. Two Sum
  • 15. 3Sum
  • 18. 4Sum
  • 410. Split Array Largest Sum
  • 560. Subarray Sum Equals K

• Calculation

idiotleon

Competitive Programming Syllabus

Geometry

• Graham Scan algorithm for Convex Hull O(n * log(n))
• Online construction of 3-D convex hull in O(n^2)
• Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn)
  • Suggested Reading - http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm
• Rotating Calipers Technique
  • Suggested Reading - http://cgm.cs.mcgill.ca/~orm/rotcal.html

• Problems - Refer the article for a list of problems which can be solved using Rotating Calipers technique.

idiotleon

class Solution{
    public cutPiles(int[] piles, int target){
        int max = 0;
        for(int pile : piles){
            max = Math.max(max, pile);
        }
        
        int lo = 1, hi = max;
        
        while(lo < hi){

idiotleon

/**
 * Time Complexity:     O(N)
 *  O(N), total number of N-arry tree nodes
 * 
 * Space Complexity:    O(W) + O(N)
 *  O(W), the maximum width of this N-arry tree
 *  O(N), consumed by the answer N-arry tree
 * 
 * 
 * Example 1: [1, null, 3, 2, 4, null, 5, 6]

idiotleon

public class SolutionAlmostEquivalentStrings{
  public String[] almostEquivalent(String[] s, String[] t){
    // sanity check
    if(s == null || t == null || s.length != t.length) return new String[0];
    
    final int N = s.length;
    String[] ans = new String[N];

    traversal: for(int i = 0; i < N; ++i){
      int[] freq = new int[26];