O(1) Time, O(1) Space for the follow up question


  • 0

    At each next, I remove the first element of the list that I'm processing.
    If the list that I'm processing doesn't have any other integer remaining, I remove the list and won't increase the 'nextlist' index.

    Otherwise, I will increase the 'nextlist' index or set it to 0, if I was processing the last list.

    public class ZigzagIterator
    {
        IList<IList<int>> list;
        int nextlist;
        public ZigzagIterator(IList<IList<int>> vec2d)
        {
            list = vec2d;
            nextlist = 0;
        }
    
        public bool HasNext()
        {
            return list.Any();
        }
    
        public int Next()
        {
            if (!HasNext()) throw new NullReferenceException("There is no Next element remaining to print.");
            int ret = list[nextlist][0];
            list[nextlist].RemoveAt(0);
    
            //if there was only one integars in the current list and it got removed, remove the whole list
            if(list[nextlist].Count==0)
            {
                list.RemoveAt(nextlist);
                //and don't increase the next list index, since the next list's index will be replaced.
            }
            else
            {
                nextlist = (nextlist == list.Count - 1) ? 0 : nextlist+1;
            }
            return ret;            
        }
    }
    

  • 0

    @yashar said in O(1) Time, O(1) Space for the follow up question:

    list.RemoveAt(nextlist)

    Please show documentation that says this is O(1). I highly doubt it.


  • 0

    @StefanPochmann You are right, I didn't notice that by each removing, the following elements' indices should be decreased by one. Thanks for looking at it and your point.


  • 0
    C

    @yashar As Stefan said, time complexity is not O(1) as titled. Thanks.


Log in to reply
 

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