Find First and Last Position of Element in Sorted Array

Submission Detail

88 / 88 test cases passed.
 Status:

Accepted
Runtime: 0 ms
Memory Usage: 44.5 MB
Submitted: 0 minutes ago
loading
Runtime Error Message:
Last executed input:
Input:
Output:
Expected:

Accepted Solutions Runtime Distribution

0.0
1.0
2.0
3.0
4.0
5.0
6.0
7.0
8.0
9.0
10.0
70
75
80
85
90
95
java
Runtime (ms)
Distribution (%)

0
1
2
3
4
5
6
7
8
9
10
70
80
90
Zoom area by dragging across this chart

Accepted Solutions Memory Distribution

43500
43750
44000
44250
44500
44750
45000
45250
45500
45750
46000
2.5
5.0
7.5
10.0
12.5
15.0
java
You are here!
Your memory usage beats 67.98 % of java submissions.
Memory (KB)
Distribution (%)

43500
43750
44000
44250
44500
44750
45000
45250
45500
45750
46000
5
10
15
Zoom area by dragging across this chart

Invite friends to challenge Find First and Last Position of Element in Sorted Array

Submitted Code: 0 minutes ago

Language: 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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
public int[] searchRange(int[] nums, int target) {
boolean found = false;
// first occurence of target
int k = binarySearch(nums,target,found);
int[] res = new int[2];
// if not found, return -1,-1
if (k == -1) {
res[0] = -1;
res[1] = -1;
return res;
}
res[0] = k;
if (nums.length == 1) {
res[1] = k;
return res;
}
// proceed to last occurence
while (k < nums.length && nums[k] == target)
k++;
res[1] = k-1;
return res;
}
public int binarySearch(int[] nums, int target, boolean found) {
int mp = nums.length/2;
int ind = 0;
if (nums.length == 0)
return -1;
// target check
if (nums[mp] == target) {
// backtrack to first occurence if found
while (mp > 0 && nums[mp] == target) {
if (mp > 0 && nums[mp-1] != target)
return mp;
mp--;
}
return mp;
}
int[] left = new int[mp];
int[] right = new int[nums.length-mp-1];
for (int i = 0; i < mp; i++)
left[i] = nums[i];
for (int i = 0; i < nums.length-mp-1; i++)
right[i] = nums[mp+i+1];
if (nums[mp] > target && found == false) {
ind = binarySearch(left,target,found);
if (ind != -1)
return ind;
}
if (nums[mp] < target && found == false)
ind = binarySearch(right,target,found);
if (ind != -1)
return (ind + mp + 1);
return -1;
}
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Back to problem