C# - DP with HashSet O(n^2) time and O(n^2) memory


  • 0
        public bool CanCross(int[] stones) 
        {
            HashSet<int>[] steps = new HashSet<int>[stones.Length];
            steps[0] = new HashSet<int>();
            steps[0].Add(0);
            
            Array.Sort(stones);
            
            for (int i = 1; i < stones.Length; i++)
            {
                steps[i] = new HashSet<int>();
                for (int j = 0; j < i; j++)
                {
                    int diff = stones[i] - stones[j];
                    if (steps[j].Contains(diff) || steps[j].Contains(diff + 1) || steps[j].Contains(diff - 1))
                    {
                        steps[i].Add(diff);
                    }
                }
            }
            
            return steps[steps.Length - 1].Count > 0;
        }
    

Log in to reply
 

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