Leetcode discuss: 715. Range Module

 Here is the link. 

First practice - C# - study and learn - copy ideas

Dec. 7, 2020
Introduction
It is hard for me to find time to work on my own practice. I have to go over 30 hard level algorithms based on Leetcode premium.

Learn from a competitive player
It is easy for me to practice the algorithm by rewriting a C# solution to fit my own need. I chose to study the code here.

Time complexity
Let K be the number of elements in ranges.
addRange and removeRange operations have O(K) complexity. queryRange has O(logK) complexity, if using binary search. But my approach is O(K).

Because addRange, removeRange adds at most 1 interval at a time, you can bound these further. For example, if there are A addRange, R removeRange, and Q queryRange number of operations respectively, we can express our complexity as O((A+R)^2 Q log(A+R)).

Space Complexity: O(A+R), the space used by ranges.

public class RangeModule {

    private List<int[]> intervals;
    
    public RangeModule() 
    {
        intervals = new List<int[]>();
    }
    
    /// AddRange - 
    /// first just add interval to the list;
    /// next sort the range by  start value. 
    /// merge intervals - overlap / non-overlap 
    public void AddRange(int left, int right)
    {
        intervals.Add(new int[] {left, right});
        
        // sort by start value - O(nlogn) - time complexity        
        intervals.Sort((x, y) => x[0].CompareTo(y[0]));
        
        int start = intervals[0][0];
        int end   = intervals[0][1];
        
        var temp = new List<int[]>();
        for(int i = 1; i < intervals.Count; i++)
        {
            int nextStart = intervals[i][0];
            int nextEnd   = intervals[i][1];
            
            // no overlap 
            if(nextStart > end)
            {
                temp.Add(new int[] {start, end});
                
                // next iteration
                start = nextStart; 
                end = nextEnd;
            }
            else
            {   // update first interval end value - leave merge for future
                end = Math.Max(end, nextEnd);
            }
        }
        
        temp.Add(new int[] {start, end});
        intervals = temp;
    }
    
    /// make sure that [left, right] is inside one of the intervals
    public bool QueryRange(int left, int right) 
    {
        for(int i = 0; i < intervals.Count; i++)
        {
            var start = intervals[i][0];
            var end   = intervals[i][1];
            
            if(IsOverlap(start, end, left, right))
            {
                int l = Math.Max(start, left);
                int r = Math.Min(end, right);
                
                if(l == left && r == right)
                {
                    return true;
                }
            }
        }
        
        return false;
    }
    
    public void RemoveRange(int left, int right) 
    {
        var temp = new List<int[]>();
        for(int i = 0; i < intervals.Count; i++)
        {
            int start = intervals[i][0];
            var end   = intervals[i][1];
            
            if(IsOverlap(start, end, left, right))
            {
                int l = Math.Max(start, left);
                int r = Math.Min(end, right);
                
                // 0, 1, 2 intervals three choices 
                if(l > start)
                {
                    temp.Add(new int[] {start, l});
                }
                
                if(r < end)
                {
                    temp.Add(new int[] {r, end});
                }
            }
            else 
            {
                temp.Add(new int[] {start, end});
            }
        }
        
        intervals = temp;
    }
    
    /// checking is to check if it is not overlapped
    /// either [start1, end1] is left side of [start2, end2], or right side of [start2, end2]
    private bool IsOverlap(int start1, int end1, int start2, int end2)
    {
        return !(start2 >= end1 || start1 >= end2);
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.AddRange(left,right);
 * bool param_2 = obj.QueryRange(left,right);
 * obj.RemoveRange(left,right);
 */