What on earth is meant by too much memory?


  • 25

    Because I've made a rather naive map-of-index-lists Java solution and it was happily accepted by the OJ. So far I see three types of solutions:

    1. Like mine, O(N) memory, O(N) init, O(1) pick.

    2. Like @dettier's Reservoir Sampling. O(1) init, O(1) memory, but O(N) to pick.

    3. Like @chin-heng's binary search: O(N) memory, O(N lg N) init, O(lg N) pick.

    Are all three kinds acceptable?


  • 0
    L
    This post is deleted!

  • 4

    @SergeyTachenov Can you show yours? Mine doesn't get accepted, gets "Memory Limit Exceeded" (with "Last executed input" having the truly gigantic nums = [1,2,3,3,3]).

    My Python:

    class Solution(object):
        def __init__(self, nums):
            self.indexes = collections.defaultdict(list)
            for i, num in enumerate(nums):
                self.indexes[num].append(i)
    
        def pick(self, target):
            return random.choice(self.indexes[target])
    

    My Java (edit half a year later: it now gets accepted):

    public class Solution {
    
        public Solution(int[] nums) {
            for (int i=0; i<nums.length; i++) {
                int num = nums[i];
                if (!indexes.containsKey(num))
                    indexes.put(num, new ArrayList<Integer>());
                indexes.get(num).add(i);
            }
        }
        
        public int pick(int target) {
            List<Integer> indexes = this.indexes.get(target);
            int i = (int) (Math.random() * indexes.size());
            return indexes.get(i);
        }
        
        private Map<Integer, List<Integer>> indexes = new HashMap<>();
    }
    

  • 2

    @StefanPochmann Mine was almost exactly like that, and now it doesn't get accepted too, although it fails on a much larger array. I think the limit was fixed somehow since I submitted.


  • 0
    P

    @StefanPochmann
    Mine first submit is the same as yours, but it exceeds the memory limited, then I try to use TreeMap, (I use java here), but it also exceeds the memory limited. Actually, I'm not sure which is more optimized in memory?

    My java:

    public class Solution {
        HashMap<Integer, TreeMap<Integer, Integer>> pos;
        public Solution(int[] nums) {
            pos = new HashMap<>();
            for(int i = 0; i < nums.length; i++) {
                if(!pos.containsKey(nums[i])) {
                    TreeMap<Integer, Integer> tree = new TreeMap<Integer, Integer>();
                    tree.put(i, 1);
                    pos.put(nums[i], tree);
                } else {
                    TreeMap<Integer, Integer> tree = pos.get(nums[i]);
                    Integer floor = tree.floorKey(i);
                    if(floor != null && i - tree.get(floor) == floor) {
                        int range = 1 + tree.get(floor);
                        tree.put(floor, range);
                    } else {
                    	tree.put(i, 1);
                    }
                }
            }
        }
        
        public int pick(int target) {
            TreeMap<Integer, Integer> tree = pos.get(target);
            int sum = 0;
            for(Integer i : tree.keySet()) {
                sum += tree.get(i);
            }
            Random r = new Random();
            int indx = r.nextInt(sum);
            int ans = -1, cur = 0, prev = 0;
            for(Integer i : tree.keySet()) {
                cur += tree.get(i);
                if(cur > indx) {
                    ans = i + indx - prev;
                    break;
                }
                prev = cur;
            }
            return ans;
        }
    }
    

    for HashMap<Integer, TreeMap<Integer, Integer>> pos; , it means
    num -> start_position -> number of the same successive digit compared to HashMap<Integer, List<Integer>> which is more optimized?


  • 2
    K

    Hi, the question is the same with Q382 Linked List Random Node, the only difference is in this question, we only count the target, and get the random index from the target indices.

    The background of the question is the data stream is very large, and we only need one target index from one data stream, the next data stream is another one, so why do we store every data stream, we just need O(1) space and O(n) time to traverse the first data stream , and O(1) space and O(n) time to traverse the second data stream....

    Have a look at the other guy's solution, it's the same with my explanation:
    https://discuss.leetcode.com/topic/58301/simple-reservoir-sampling-solution


  • 1

    @pirate Of course HashMap and ArrayList are more optimized. TreeMap is a red-black-tree with lots of pointers, which means both slow and memory consuming.


  • 3

    @SergeyTachenov I didn't read this article, but its summary says:

    • HashMap takes 32 * SIZE + 4 * CAPACITY bytes
    • TreeMap takes 40 * SIZE bytes.

    With CAPACITY being about 4/3 to 8/3 times as large as SIZE, that's pretty close. A HashMap might take more memory.


  • 0

    @StefanPochmann I stand corrected then.


  • 0
    C

    Implemented the map of index list in C++ and also got Memory Limit Exceeded
    Also wondering why this is not accepted but my O(N) memory solution is accepted


  • 0

    I got two more complicated O(n) + O(1) solution now that consistently get accepted. I only tried Python, but I think it might work in other languages as well (at least my "original" way there).


  • 0

    I'm using map with <value, vector<index>> in C++, but get rejected by the OJ with error memory limited exceeds.

    Same problem here, I think my solution is O(N) memory. (But I guess since you have to store all the values as the key, the actual memory in worst cases can be 2 times of original array, when all numbers are different)

    I guess the problem just want us to use reservoir sampling.


  • 0

    @SergeyTachenov Implemented the same code in C++ that uses O(1) memory but still doesn't get accepted...

    class Solution {
        vector<int> v; vector<int>& vect = v;
        int n;
    public:
        Solution(vector<int> nums){
            vect = nums;
            n = nums.size();
        }
        int pick(int t) {
            int count = 0, res = -1;
            for(int i = 0; i < n; i++) {
                if (vect[i] == t) {
                    count += 1;
                    if (not (rand() % count)) 
                        res = i;
                }
            }
            return res;
        }
    };
    
    

  • 1

    @agave I just submitted that three times and it got accepted every time.

    I don't think it's O(1) memory, though. I think your vect = nums; still copies the vector and that your vector<int>& vect = v doesn't do what you think it does. I think it's just an alias. You can also change vect[i] to v[i] and it still works. If you really want O(1) space, I think a pointer to the given vector or begin+end iterators or begin iterator plus size is the way to go. But if you can tell or show more about your way and why you think it's O(1), I'd be very interested :-)


  • 0

    @StefanPochmann I'm a bit rusty on C++... I think I'll use iterators.
    You submitted the C++ and got accepted? Or the Java code?


  • 0

    @agave I submitted your C++ solution.


  • 0

    @StefanPochmann Yeah now it gets accepted... Geez... Not sure what's going on...


  • 0

    @StefanPochmann So now I changed the code and added begin() iterator, but it's not working properly. Seems like the iterator is not dereferencing appropriately.

    class Solution {
        vector<int>::iterator beg;
        int n;
    public:
        Solution(vector<int> nums){
            beg = nums.begin();
            n = nums.size();
        }
        int pick(int t) {
            int count = 0, res = -1;
            for(int i = 0; i < n; i++) {
                if (*(beg + i) == t) {
                    count += 1;
                    if (not (rand() % count)) 
                        res = i;
                }
            }
            return res;
        }
    };
    

  • 1

    @agave Ah, right, actually already the Solution(vector<int> nums){ causes a copy to be made, and then you're storing an iterator to the copy, but the copy gets destroyed at the end of your constructor. If I'm not mistaken :-). I'm no C++ expert, either. I tried Solution(vector<int> &nums){ but then I have trouble storing the iterator...


  • 1

    @StefanPochmann Exactly, you're right... You get the address of the copy, which gets destroyed. So we need to make a copy anyway, unless the constructor passes us the reference.


Log in to reply
 

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