# Neat O(N) Java solution

• Of coz using binary search could reduce the time complexity from O(N) to O(logN). However, the O(N) solution has clear logic and is easy to understand

``````public class SummaryRanges {
private List<Integer> bottom;
private List<Integer> top;

/** Initialize your data structure here. */
public SummaryRanges() {
bottom=new ArrayList<Integer>();
top=new ArrayList<Integer>();
}

if(bottom.size()==0){
return;
}
//val is larger than or equal to the start of the last interval
if(val==bottom.get(bottom.size()-1)) return;
if(val>bottom.get(bottom.size()-1)){
if(val<=top.get(bottom.size()-1)) return;
if(val-top.get(bottom.size()-1)==1){
top.set(bottom.size()-1,val);
return;
}
}
//val is smaller than or equal to the start of the first interval
if(val==bottom.get(0)) return;
if(val<bottom.get(0)){
if(bottom.get(0)-1==val){
bottom.set(0,val);
return;
}
}
//val is in between
int i=0;//position of val
while(bottom.get(i)<val){
i++;
}
if(bottom.get(i)==val||top.get(i-1)>=val) return;
if(bottom.get(i)-1==val&&top.get(i-1)+1==val){
bottom.remove(i);
top.remove(i-1);
return;
}
if(bottom.get(i)-1==val){
bottom.set(i,val);
return;
}
if(top.get(i-1)+1==val){
top.set(i-1,val);
return;
}
}

public List<Interval> getIntervals() {
List<Interval> res=new ArrayList();
for(int i=0;i<bottom.size();i++){