/
Main.java
96 lines (76 loc) · 2.38 KB
/
Main.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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
package edu.northeastern.ashish;
import java.util.ArrayList;
//https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
public class Main {
public static void main(String[] args) {
int[] arr = {5,7,7,8,8,10};
int[] result = findFirstAndLast(arr, 7);
if(result != null){
System.out.println("First Position = " + result[0]);
System.out.println("Last Position = " + result[1]);
}else{
System.out.printf("Element not found");
}
}
private static int[] findFirstAndLast(int[] arr, int x){
if(arr == null){
return null;
}
int firstIndex = findFirstPosition(arr, x);
if(firstIndex == -1){
return null;
}
int lastIndex = findLastPosition(arr, x);
return new int[]{firstIndex, lastIndex};
}
public static int findFirstPosition(int[] arr, int x){
return findFirstPosition(arr, x, 0, arr.length -1);
}
private static int findFirstPosition(int[] arr, int x, int low, int high){
if(low > high){
return -1;
}
if(arr[high] < x){
return -1;
}
if(arr[low] > x){
return -1;
}
if(arr[low] == x && arr[high] == x){
return low;
}
int mid = (low + high)/2;
if(arr[mid] < x){
return findFirstPosition(arr, x, mid +1, high);
}else if (arr[mid] > x){
return findFirstPosition(arr, x, low, mid -1);
}else{
return findFirstPosition(arr, x, low, mid -1) ;
}
}
public static int findLastPosition(int[] arr, int x){
return findLastPosition(arr, x, 0, arr.length -1);
}
private static int findLastPosition(int[] arr, int x, int low, int high){
if(low > high){
return -1;
}
if(arr[high] < x){
return -1;
}
if(arr[low] > x){
return -1;
}
if(arr[low] == x && arr[high] == x){
return high;
}
int mid = (low + high)/2;
if(arr[mid] < x){
return findLastPosition(arr, x, mid +1, high);
}else if (arr[mid] > x){
return findLastPosition(arr, x, low, mid -1);
}else{
return findLastPosition(arr, x, mid, high -1 ) ;
}
}
}