Wrong complexity for Create Insert Delete GetRandom O(1) problem

The problem statement says, that all three operations should take O(1) time on average.
However the current implementation is only O(n) on average. It might have passed the Leetcode submission, as their tests are usually not strong. But the code logic is technically still wrong...

Both the C++ and the Python versions are affected:

leetcode-problem-solving/June Challenge/CPP/Insert Delete GetRandom O(1) Solution

Lines 56 to 70 in 9329dc4

    
           /** Removes a value from the set. Returns true if the set contained the specified element. */ 
        
           bool remove(int val) { 
        
               if(ss.find(val) == ss.end()) 
        
                   return false; 
        
               ss.erase(val); 
        
               for (int i = 0;i < a.size();i++) { 
        
                   if(a[i] == val) { 
        
                       a[i] = a[a.size() - 1]; 
        
                       a.pop_back(); 
        
                       break; 
        
                   } 
        
               } 
        
               return true; 
        
           }

leetcode-problem-solving/June Challenge/Python/Insert Delete GetRandom O(1) Solution.py

Lines 21 to 34 in 9329dc4

    
               def remove(self, val: int) -> bool: 
        
                   """ 
        
                   Removes a value from the set. Returns true if the set contained the specified element. 
        
                   """ 
        
                   if val not in self.ss: 
        
                       return False 
        
                   self.ss.discard(val) 
        
                   for i, ai in enumerate(self.a): 
        
                       if ai == val: 
        
                           self.a[i] = self.a[-1] 
        
                           self.a.pop() 
        
                           break 
        
                   return True

The python version is just implementation of c++ version and doesn't has its own exitence.

Navigation Menu

Repository navigation

Wrong complexity for Create Insert Delete GetRandom O(1) problem #15

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

	/** Removes a value from the set. Returns true if the set contained the specified element. */
	bool remove(int val) {

	if(ss.find(val) == ss.end())
	return false;
	ss.erase(val);
	for (int i = 0;i < a.size();i++) {
	if(a[i] == val) {
	a[i] = a[a.size() - 1];
	a.pop_back();
	break;
	}
	}
	return true;
	}

	def remove(self, val: int) -> bool:
	"""
	Removes a value from the set. Returns true if the set contained the specified element.
	"""
	if val not in self.ss:
	return False

	self.ss.discard(val)
	for i, ai in enumerate(self.a):
	if ai == val:
	self.a[i] = self.a[-1]
	self.a.pop()
	break
	return True

Wrong complexity for Create Insert Delete GetRandom O(1) problem #15

Description

Activity

harshraj22 commented on Jun 17, 2020

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions