JavaScript (Find Minimum in Rotated Sorted Array)

Question

I have a leetcode question that I tried to use my own method to solve it, but I got an error and I don't know what's wrong.

This is the topic:

This is my attempted solution:

var findMin = function(nums) {
    if (nums.length === 0) return undefined;
    var minEle = nums[0];
    if (nums.length === 1) {
        minEle = nums[0];
        return minEle;
    }
    var start = 0;
    var end = nums.length - 1;
    if (nums[end] > nums[start]) {
        end = Math.floor(end / 2);
    } else {
        start = Math.ceil(end / 2);
    }
    findMin(nums.slice(start, end + 1));
};

findMin([3,4,5,1,2]);

and the output is undefined.

I tried this too :

var findMin = function(nums) {
    if (nums.length === 0) return undefined;
    var minEle = nums[0];
    if (nums.length === 1) {
        minEle = nums[0];
        return minEle;
    }
    var start = 0;
    var end = nums.length - 1;
    if (nums[end] > nums[start]) {
        end = Math.floor(end / 2);
    } else {
        start = Math.ceil(end / 2);
    }
    findMin(nums.slice(start, end + 1));
    return minEle;
};

findMin([3,4,5,1,2]);

And the output is 3.

I tried to debug it and I got this:

I don't understand why my recursion solution is not correct. Note that I tried to implement a solution with consideration of time complexity.

Unmitigated · Accepted Answer · 2020-06-23 23:12:10Z

1

You are missing the last return statement when recursing.

return findMin(nums.slice(start, end + 1)); //added return here

var findMin = function(nums) {
    if (nums.length === 0) return undefined;
    var minEle = nums[0];
    if (nums.length === 1) {
        minEle = nums[0];
        return minEle;
    }
    var start = 0;
    var end = nums.length - 1;
    if (nums[end] > nums[start]) {
        end = Math.floor(end / 2);
    } else {
        start = Math.ceil(end / 2);
    }
    return findMin(nums.slice(start, end + 1));
};

console.log(findMin([3,4,5,1,2]));

answered Jun 23, 2020 at 23:12

Unmitigated

91.5k12 gold badges103 silver badges109 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Laode Muhammad Al Fatih · Accepted Answer · 2020-06-23 23:04:48Z

1

If you want to find the smallest value in an array, just use Math.min.

Example:

console.log(Math.min.apply(null, [3,4,5,1,2]))

answered Jun 23, 2020 at 23:04

Laode Muhammad Al Fatih

4,7001 gold badge22 silver badges40 bronze badges

1 Comment

hongkongbboy Over a year ago

Thank you, but I tried to implement a solution with consideration of Time Complexity.

Mike Rivet · Accepted Answer · 2020-06-23 23:11:38Z

I don't think recursion is necessary for this one. At a high level we just need to go through each element and find the smallest. This could be done pretty simply with a for loop and a variable to store the smallest seen value.

var findMin = function(nums) {
    if(nums.length === 0) {
        return undefined;
    }
    if(nums.length === 1) {
        return nums[0];
    }
    // initialize the smallest number placeholder to the first value
    let smallestNum = nums[0];
    
    for(let i = 1; i < nums.length; i++) {
        if(smallestNum > nums[i]) {
            smallestNum = nums[i];
        }
    }
    return smallestNum;
}

This could be simplified with an array reducer, but the logic would be the same.

Another approach could be to assume the numbers will be ascending and once you find a number that is smaller return it. For example, in [3,4,5,1,2] it increases until we go from 5 to 1.

var findMin = function(nums) {
    if(nums.length === 0) {
        return undefined;
    }
    if(nums.length === 1) {
        return nums[0];
    }

    for(let i = 1; i < nums.length; i++) {
        if(nums[0] > nums[i]) {
            return nums[i];
        }
    }
    return nums[0];
}

In this case as soon as we find a number that is smaller than the first we break the loop. If we get all the way through the array we know the first number was the smallest.

JEQP · Accepted Answer · 2020-06-23 23:24:25Z

0

I'm not at a rank to comment, so I have to post as an answer. It seems you're changing "end" and "start" in the if conditions, but then you're calling the function again and the function resets those variables to

var start = 0;
var end = nums.length - 1;

So whatever is changed in the second if/else statement, start will get reset to 0, and end will halve. But maybe I've missed something, so if this is irrelevant please ignore.

answered Jun 23, 2020 at 23:24

JEQP

1101 silver badge6 bronze badges

Collectives™ on Stack Overflow

JavaScript (Find Minimum in Rotated Sorted Array)

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

1 Comment

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related