C# practice - using sorted array to help


  • 0

    Worked on linear solution first, tried to use O(n) time complexity solution over 20 minutes. Tried to linear scan the array from left to right, I had the issue to determine the start position of searched subarray, need to do backward tracking. Too complicated for an easy level algorithm, I gave up.

    C# code needs some code review.

    Using sorted array to solve the problem. No time out

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;
    
    namespace Leetcode581_shortestUnsortedContinuousSubarray
    {    
        /// <summary>
        /// https://leetcode.com/contest/leetcode-weekly-contest-32/problems/shortest-unsorted-continuous-subarray/#_=_
        /// </summary>
        class Leetcode581_shortestUnsortedContinuousSubarray
        {
            static void Main(string[] args)
            {
                RunTestcase(); 
            }
    
            public static void RunTestcase()
            {
                int[] numbers = new int[] {1, 2, 3,4 };
                FindShortestUnsortedContinuousSubarray(numbers); 
            }
    
            /// <summary>
            /// array's length is in range [1, 10,000]. 
            /// 
            /// </summary>
            /// <param name="numbers"></param>
            /// <returns></returns>
            public static int FindShortestUnsortedContinuousSubarray(int[] numbers)
            {
               int length = numbers.Length;
               int[] sorted = new int[length]; 
               Array.Copy(numbers, sorted, length);
               Array.Sort(sorted);
    
               int start = 0;
               bool foundStart = false; 
               for (int i = 0; i < length; i++)
               {
                   var current = sorted[i];
                   var compare = numbers[i];
                   if (current == compare)
                   {
                       continue;
                   }
                   else
                   {
                       start = i;
                       foundStart = true; 
                       break; 
                   }
               }
    
               if (!foundStart)
               {
                   return 0; 
               }           
    
               int  end = length - 1; 
               for (int i = length - 1; i >= start; i--)
               {
                   var current = sorted[i];
                   var compare = numbers[i];
                   if (current == compare)
                   {
                       continue;
                   }
                   else
                   {
                       end = i;
                       break; 
                   }
               }
    
               return end - start + 1; 
            }
        }
    }

Log in to reply
 

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