Please Help! Memory Limit exceeded. C# code


  • 0
    J

    The solution I used gives a memory limit exceeded message for this input : [[1,2,1],[2147483646,2147483647,2147483647]]

    The idea I used is to create a dictionary that contains the x coordinates as keys and the height at that coordinate as the value. In the first loop, I go through each of the arrays in buildings (corresponding to one building) and then within those x coordinates, I store the height(done within the inner loop.) After I populate the dictionary, I then go through all the values in the dictionary, and store any coordinate where the height changes.

    For the input above, my dictionary is supposed to have four entries
    1 -> 1
    2 -> 1
    3 -> 0
    2147483646 -> 2147483647
    2147483647 -> 2147483647

    This is my code.

    public IList<int[]> GetSkyline(int[,] buildings) 
        {
            var result = new List<int[]>();
            if (buildings.GetLength(0) == 0) return result;
            
            if (buildings.GetLength(0) == 1)
            {
                result.Add(new int[]{buildings[0,0], buildings[0,2]});
                result.Add(new int[]{buildings[0,1],0});
                return result;
            }
            
            // This dictionary will contain all the x-coordinates as key and the max height at that point considering all points
            // as values. In the for loop below, we will populate the dictionary. 
            var dic = new Dictionary<int, int>();
            for(int index = 0; index < buildings.GetLength(0); index++)
            {
                var firstxcoor = buildings[index,0];
                var secondxcoor = buildings[index,1];
                var height = buildings[index,2];
                for (int i = firstxcoor; i <= secondxcoor; i++)
                {
                    if (dic.ContainsKey(i))
                    {
                        dic[i] = Math.Max(dic[i], height);
                    }
                    else
                    {
                        dic.Add(i, height);
                    }
                }
                // This is to handle cases where there is a building by itself away from others, I need to store the next x-coordinate and a value zero. If that value is encountered sometime later, the value 0 will be overridden lso anyway. Also convers the last building case. 
                if (!dic.ContainsKey(secondxcoor+1) && secondxcoor+1 <= int.MaxValue) dic.Add(secondxcoor+1, 0);
            }
            
            foreach (var value in dic.Keys)
            {
                // just for debugging
                Console.WriteLine(value + " : " + dic[value]);
            }
            
            // Now, we loop through all the coordinates in the dictionary, and mark a point when there is a change in height 
            // at that point and the previous point, and add it to our list, along with it's height.
            
            var previous = 0;
            foreach (var xcoordinate in dic.Keys)
            {
                if (dic[xcoordinate] != previous)
                {
                    if (dic[xcoordinate] > previous)
                    {
                        result.Add(new int[]{xcoordinate, dic[xcoordinate]});
                        previous = dic[xcoordinate];
                    }
                    else if (dic[xcoordinate] < previous)
                    {
                        result.Add(new int[]{xcoordinate-1, dic[xcoordinate]});
                        previous = dic[xcoordinate];
                    }
                    // The reason we are checking if the previous value is less than or greater than the   current height is because
                    // based on problem statement, when the height decreases, we need to mark that point with new height, but this
                    // algorithm will determine that at the next point.
                }
            }
            return result;
        }
    

    I have been trying to understand why this won't work.

    NOTE: I know this might not be the most efficient code, but I was trying to implement my own idea. Please suggest any improvements in terms of performance or the algorithm too.

    Thanks in advance for any help.


Log in to reply
 

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