I was trying out this problem link.

So we have a list of (key,timestamp,value), where a single key can have multiple (timestamp,value) pairs , and we have to find the greatest timestamp <= a given timestamp and matching a given key. Also the list is provided with an increasing timestamp, so basically its sorted based on timestamp.

My initial solution( say solution 1) to this problem was making a HashMap<String,ArrayList<Pair<Integer,String>>>, so i can lookup the key and binary search the arraylist to find a timestamp satisfying the condition.

class TimeMap {
    HashMap<String,ArrayList<Pair<Integer,String>>> map;
    public TimeMap() {
        map=new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        Pair<Integer,String> pair=new Pair<Integer,String>(timestamp,value);
        if(map.containsKey(key)) 
            map.get(key).add(pair);
        else{
            ArrayList<Pair<Integer,String>> l=new ArrayList<>();
            l.add(pair);
            map.put(key,l);
        }
    }
    public String get(String key, int t) {
        if(!map.containsKey(key)) return "";
        ArrayList<Pair<Integer,String>> x=map.get(key);
        int ans=func(x,t,0,x.size()-1,new int[1]);
        return ans==-1?"":x.get(ans).getValue();
    }
    private Integer func(ArrayList<Pair<Integer,String>> x,int t,int i, int j,int[] max){
        if(i>j) return -1;
        int mid=i+(j-i)/2;
        if(x.get(mid).getKey()>t) return func(x,t,i,mid-1,max);
        max[0]=Math.max(max[0],mid);
        func(x,t,mid+1,j,max);
        return max[0];
    }
}

Another solution is putting all (key,timestamp,value) objects in a single ArrayList and linear search for an object satisfying the condition. Binary search is not possible because we have to look for timestamp that also satisfies a key, and its not possible to determine which half the an object with a matching key might be based on timestamp alone.

class TimeMap {
    ArrayList<MyClass> arr;
    int size;
    class MyClass implements Comparable<MyClass>{
        String key;
        String value;
        int timestamp;
        public MyClass(String key,String value,int timestamp){
            this.key=key;
            this.value=value;
            this.timestamp=timestamp;
        }

        @Override
        public int compareTo(MyClass other) {
            return this.timestamp==other.timestamp?0:this.timestamp>other.timestamp?1:-1;
        }
    }
    public TimeMap() {
        arr=new ArrayList<>();
        this.size=0;
    }
    
    public void set(String key, String value, int timestamp) {
        MyClass x=new MyClass(key,value,timestamp);
        arr.add(x);
        size++;
    }
    public String get(String key, int t) {
        return func(key,t);
    }
    private String func(String key,int t){
        for(int i=size-1;i>=0;i--){
            MyClass x=arr.get(i);
            if(x.key.equals(key) && x.timestamp<=t) return x.value;
        }
        return "";
    }
}

Now even if we ignore not applying binary search in the second case, if it were possible, the second solution is performing better. Can someone explain why that is the case. Also, please feel free to point out if im doing something wrong that is not general practice,etc.