Find Minimum in Rotated Sorted Array

[Hungry_DinoBaby]

1 hour ago, Nimmakai said:

It is a modified binary search problem 

cc @friesNfrappe

Are u able to solve this problem? 
 

edhi medium level, naku easy level ke vachipothundi 🤒
 

[Nimmakai]

4 minutes ago, Hungry_DinoBaby said:

Are u able to solve this problem? 
 

Vere similar problem chesa, like oka number istadu, a number ni e twisted array lo ekada undo index return cheyali.. so twisted array ante binary search gurthochindhi. Arrays lo medium idi

[Hungry_DinoBaby]

Just now, Nimmakai said:

Vere similar problem chesa, like oka number istadu, a number ni e twisted array lo ekada undo index return cheyali.. so twisted array ante binary search gurthochindhi. Arrays lo medium idi

Cool. Atleast you have an idea. 

[mmharshaa]

14 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]

my logic should work for your inputs. Only cases i didn't cover were one and zero elements

[Vaampire]

public class Solution {
    public int FindMin(int[] nums) {
       int left = 0;
        int right = nums.Length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] < nums[right]) right = mid;
            else if(nums[mid] > nums[right]) left = mid + 1;
            else right--;
        }
        return nums[left];
    }
}

[Vaampire]

Just now, Vaampire said:

public class Solution {
    public int FindMin(int[] nums) {
       int left = 0;
        int right = nums.Length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            if(nums[mid] < nums[right]) right = mid;
            else if(nums[mid] > nums[right]) left = mid + 1;
            else right--;
        }
        return nums[left];
    }
}

Copied from my leetcode solutions. Eppudo 4 yrs back chesa

[johnydanylee]

@Arey_enti_ra_idi

[Hungry_DinoBaby]

8 hours ago, johnydanylee said:

@Arey_enti_ra_idi

Vuuuu

[dasari4kntr]

my logic....kind of overkilled...but working...

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    
    if(nums && nums.length===1) {
        return nums[0];
    }
    
    if(nums && nums.length>1) {
        const middle = nums.length/2;
        const left = nums.slice(0, middle);
        const right = nums.slice(middle);
        return findMin(left) > findMin(right) ? findMin(right) : findMin(left);
    }
    
};

 

[Vaampire]

18 minutes ago, dasari4kntr said:

my logic....kind of overkilled...but working...

 

/**
 * @param {number[]} nums
 * @return {number}
 */
var findMin = function(nums) {
    
    if(nums && nums.length===1) {
        return nums[0];
    }
    
    if(nums && nums.length>1) {
        const middle = nums.length/2;
        const left = nums.slice(0, middle);
        const right = nums.slice(middle);
        return findMin(left) > findMin(right) ? findMin(right) : findMin(left);
    }
    
};

 

This works but complexity is O(n). 
if i understood ur solution correctly, u r totally ignoring the fact that its rotated sorted array.  Ur solution will work even for unsorted array.

recursive alg should be used very cautiously.

also ur solution used extra space too by coping elements into variables..

 

sorry, dint mean to discourage you. I am just giving feed back as an interviewer

[Nimmakai]

1 minute ago, Vaampire said:

This works but complexity is O(n). 
if i understood ur solution correctly, u r totally ignoring the fact that its rotated sorted array.  Ur solution will work even for unsorted array.

recursive alg should be used very cautiously.

also ur solution used extra space too by coping elements into variables..

 

sorry, dint mean to discourage you. I am just giving feed back as an interviewer

@Vaampire bro 3 years  experience petkoni jobs apply chesthe , leetcode lo nunchi medium a adgutara or hard kuda na ?

[Marsmangalodu]

Binary search variation O(log n) tho cheyyali ani intervier expectation

[Vaampire]

29 minutes ago, Nimmakai said:

@Vaampire bro 3 years  experience petkoni jobs apply chesthe , leetcode lo nunchi medium a adgutara or hard kuda na ?

Leetcode hard medium or easy totally depends on interviewer. 
manchollu avuthey hard eppudu adagaru general gaa. Also lc rating doesnt make sense. Konni easy probs ki hard tag pettadu. Vice versa too

[dasari4kntr]

1 hour ago, Vaampire said:

This works but complexity is O(n). 
if i understood ur solution correctly, u r totally ignoring the fact that its rotated sorted array.  Ur solution will work even for unsorted array.

recursive alg should be used very cautiously.

also ur solution used extra space too by coping elements into variables..

 

sorry, dint mean to discourage you. I am just giving feed back as an interviewer

ok..got it...

[Chay]

16 hours ago, Hungry_DinoBaby said:

Are u able to solve this problem? 
 

edhi medium level, naku easy level ke vachipothundi 🤒
 

ayyo watch poyinda