Tuesday, September 22, 2020

Find Minimum in Rotated Sorted Array with duplicates

Problem: It is same as previous Find Minimum in Rotated Sorted Array but here the array contains duplicates. 

Approach: We just need one additional check to make it work in this case which is - if arr[mid] is equals to arr[high] then we just reduce high by 1.

        public int FindMinInRotatedArray(int[] nums)

        {

            if (nums?.Length == 0)

            {

                return -1;

            }

            int low = 0, high = nums.Length - 1;

            while(low < high)

            {

                int mid = (low + high) / 2;

                if (nums[mid] == nums[high]) // Additional check

                {

                    --high;

                }

                else if (nums[mid] > nums[high])

                {

                    low = mid + 1;   

                }

                else

                {

                    high = mid;

                }

            }

            return nums[high];

        }

No comments:

Post a Comment