Find Minimum in Rotated Sorted Array

[dasari4kntr]

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums, return the minimum element of this array.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

 

 

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

[usetime63]

@lucky7 @Sullicheekusulliga

[Nimmakai]

It is a modified binary search problem 

cc @friesNfrappe

[ChinnaBhasha]

I would do temp = a[0], 

foreach element{ifa[n]<a[n-1] return a[n]}

return temp;

😀

[Telugodura456]

take the first value of array and call it X. And  have an iterator at the last value of array. Keep iterating the iterator from right to left as long as value of iterator is less than X. THe moment value becomes more than X then the last value pointed by iterator is minimum. ALso the number of times you iterated is number of rotations.

Etlundhi solution!

[jambalhaatraja]

I pity how many engineers are not even thinking of entrepreneurship innovation creativity in their life and just getting stuck for ages together in this LC HR problems. 

[mmharshaa]

for(int i=0;i<nums.size-1;i++)

{

if(nums[i]>nums[i+1])

{

return nums[i+1];

}

}

return nums[0];

 

 

[pachimirchi]

class Solution:
    def findMin(self, nums: List[int]) -> int:
        pos=0
        for i in range(0,len(nums)):
            try:
                if nums[i]>nums[i+1]:
                    pos=i
                    break
            except:
                return nums[0]
            
                    
        orig=nums[pos+1:]+nums[0:pos+1]
        return orig[0]

[Vaampire]

39 minutes ago, ChinnaBhasha said:

I would do temp = a[0], 

foreach element{ifa[n]<a[n-1] return a[n]}

return temp;

😀

Recruiter will say thank you for ur interest but unfortunately we decided not to proceed with you at this time

[ChinnaBhasha]

Just now, Vaampire said:

Recruiter will say thank you for ur interest but unfortunately we decided not to proceed with you at this time

haha, I know. 😂

[Vaampire]

46 minutes ago, Nimmakai said:

It is a modified binary search problem 

Solution kooda pretty much binary search ey. If conditions lo inko condition add avutbadhi

[Vaampire]

35 minutes ago, mmharshaa said:

for(int i=0;i<nums.size-1;i++)

{

if(nums[i]>nums[i+1])

{

return nums[i+1];

}

}

return nums[0];

 

 

Complexity O(n)

 

[k2s]

57 minutes ago, dasari4kntr said:

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:

• [4,5,6,7,0,1,2] if it was rotated 4 times.
• [0,1,2,4,5,6,7] if it was rotated 7 times.

Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].

Given the sorted rotated array nums, return the minimum element of this array.

 

Example 1:

Input: nums = [3,4,5,1,2]
Output: 1
Explanation: The original array was [1,2,3,4,5] rotated 3 times.

Example 2:

Input: nums = [4,5,6,7,0,1,2]
Output: 0
Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times.

Example 3:

Input: nums = [11,13,15,17]
Output: 11
Explanation: The original array was [11,13,15,17] and it was rotated 4 times. 

 

 

The array may contain duplicates.

Example 1:

Input: [1,3,5]
Output: 1

Example 2:

Input: [2,2,2,0,1]
Output: 0

Nice.

Use heap and get O(1)*O(k) complexity 

[dasari4kntr]

56 minutes ago, Nimmakai said:

It is a modified binary search problem 

cc @friesNfrappe

 

50 minutes ago, ChinnaBhasha said:

I would do temp = a[0], 

foreach element{ifa[n]<a[n-1] return a[n]}

return temp;

😀

 

50 minutes ago, Telugodura456 said:

take the first value of array and call it X. And  have an iterator at the last value of array. Keep iterating the iterator from right to left as long as value of iterator is less than X. THe moment value becomes more than X then the last value pointed by iterator is minimum. ALso the number of times you iterated is number of rotations.

Etlundhi solution!

 

48 minutes ago, jambalhaatraja said:

I pity how many engineers are not even thinking of entrepreneurship innovation creativity in their life and just getting stuck for ages together in this LC HR problems. 

 

43 minutes ago, mmharshaa said:

for(int i=0;i<nums.size-1;i++)

{

if(nums[i]>nums[i+1])

{

return nums[i+1];

}

}

return nums[0];

 

 

 

18 minutes ago, pachimirchi said:

class Solution:
    def findMin(self, nums: List[int]) -> int:
        pos=0
        for i in range(0,len(nums)):
            try:
                if nums[i]>nums[i+1]:
                    pos=i
                    break
            except:
                return nums[0]
            
                    
        orig=nums[pos+1:]+nums[0:pos+1]
        return orig[0]

 

3 minutes ago, k2s said:

Nice.

Use heap and get O(1)*O(k) complexity 

 

 

i will lift this thread tommrrow...

my logic is failing with [-1,-1,-1,-1] input...once i solve that..i will lift it again...

 

BTW..if any one want to practice...sample inputs as below..to test your code..for edge cases...

[1]

[3,1]

[1,1]

[2,2,2,0,1]

[Hungry_DinoBaby]

3 minutes ago, dasari4kntr said:

 

 

 

 

 

 

 

 

i will lift this thread tommrrow...

my logic is failing with [-1,-1,-1,-1] input...once i solve that..i will lift it again...

 

BTW..if any one want to practice...sample inputs as below..to test your code..for edge cases...

[1]

[3,1]

[1,1]

[2,2,2,0,1]

Following