LeetCode - Algorithms - 34. Find First and Last Position of Element in Sorted Array

Problem

34. Find First and Last Position of Element in Sorted Array

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int lo = 0;
        int hi = nums.length - 1;
        while (lo<=hi) {
            int mid = lo + (hi - lo) / 2;
            if (target < nums[mid])
                hi = mid-1;
            else if (target > nums[mid])
                lo = mid+1;
            else {
                int startPos = mid;
                int endPos = mid;
                while(startPos>=0 && nums[startPos]==nums[mid]) startPos--;
                while(endPos<=nums.length - 1 && nums[endPos]==nums[mid]) endPos++;
                int[] r = new int[2];
                r[0] = startPos+1;
                r[1] = endPos-1;
                return r;
            }
        }

        int[] r = {-1, -1};
        return r;       
    }
}

Submission Detail

  • 88 / 88 test cases passed.
  • Runtime: 0 ms, faster than 100.00% of Java online submissions for Find First and Last Position of Element in Sorted Array.
  • Memory Usage: 44.5 MB, less than 6.38% of Java online submissions for Find First and Last Position of Element in Sorted Array.

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    var lo = 0, hi = nums.length-1;
    while (lo<=hi) {
        var mid = lo + Math.floor((hi-lo)/2);
        if (target < nums[mid])
            hi = mid-1;
        else if (target > nums[mid])
            lo = mid+1;
        else {
            var startPos = mid, endPos = mid;
            while(startPos>=0 && nums[startPos]==nums[mid]) startPos--;
            while(endPos<=nums.length - 1 && nums[endPos]==nums[mid]) endPos++;
            return [startPos+1, endPos-1];
        }
    }

    return [-1, -1];    
};

Submission Detail

  • 88 / 88 test cases passed.
  • Runtime: 92 ms, faster than 7.49% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.
  • Memory Usage: 34.9 MB, less than 100.00% of JavaScript online submissions for Find First and Last Position of Element in Sorted Array.