Very simple O(m + log n) Java solution, beats 100%. Only iterate through relevant logs


  • 0
    P

    O(m + log n) where m is relevant logs and n is total keys. We keep a TreeMap of timestamp -> List<id> and iterate through only the relevant portion of the TreeMap using tailMap and headMap

    We round the given range to given granularity before iterating. For example, given granularity of "Day" and range of [2017:06:30:13:47:23, 2017:07:01:09:12:53], we round the range to [2017:06:30:00:00:00, 2017:07:01:23:59:59]

    public class LogSystem {
        final TreeMap<String, List<Integer>> map = new TreeMap<>();
        static final String[] graMin = new String[] {"01", "01", "00", "00", "00"};
        static final String[] graMax = new String[] {"12", "31", "23", "59", "59"};
        static final Map<String, Integer> graMap;
        
        static {
            graMap = new HashMap<>();
            graMap.put("Year", 0);
            graMap.put("Month", 1);
            graMap.put("Day", 2);
            graMap.put("Hour", 3);
            graMap.put("Minute", 4);
            graMap.put("Second", 5);
        }
        
        public LogSystem() {
        }
        
        public void put(int id, String timestamp) {
            if (!map.containsKey(timestamp)) map.put(timestamp, new ArrayList<>());
            map.get(timestamp).add(id);
        }
        
        public List<Integer> retrieve(String s, String e, String gra) {
            List<Integer> result = new LinkedList<>();
            StringBuilder ssb = new StringBuilder(), esb = new StringBuilder();
            for (int i = 0; i <= graMap.get(gra); i++) ssb.append(s.split(":")[i] + ":");
            for (int i = 1 + graMap.get(gra); i < 6; i++) ssb.append(graMin[i-1] + ":");
            for (int i = 0; i <= graMap.get(gra); i++) esb.append(e.split(":")[i] + ":");
            for (int i = 1 + graMap.get(gra); i < 6; i++) esb.append(graMax[i-1] + ":");
            Iterator<List<Integer>> iterator = map.tailMap(ssb.deleteCharAt(ssb.length() - 1).toString(), true)
                .headMap(esb.deleteCharAt(esb.length() - 1).toString(), true).values().iterator();
            while (iterator.hasNext()) result.addAll(iterator.next());
            return result;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.