Given input (items = 6, position = 3)

creates a row of 6 items and a character positioned on item 3 {0,1,2,[3],4,5}

A call to LEFT moves the character two positions to the left and the item at position 3 is removed {0,[1],2,4,5}

The next call to RIGHT moves the character two positions to the right and the item at position 1 is removed {0,2,[4],5}

Then calling position() method now should return 4.

The character will not move to the left or right if no items are present so no need to implement that.

public class MyClass {
    int position;
    int[] items;
    public MyClass(int n, int position) {
        this.position = position;
        items = new int[n];
        for(int i=0; i<n; i  ) {
            items[i] = i;
        }
    }
}

public void left() {
    int p = this.position;
    items[p] = -1;
    for(int z=0; z<2;) {
        p--;
        int value = arr[p];
        if(value != -1) {
            z  ;
        }
    }
    this.position = p;
}

public void right() {
    int p = this.position;
    items[p] = -1;
    for(int z=0; z<2;) {
        p  ;
        int value = arr[p];
        if(value != -1) {
            z  ;
        }
    }
    this.position = p;
}

public int position() {
    return arr[position];
}

This code works perfectly for small inputs, but I am getting performance errors when input is large. How to implement this efficiently. I don't have test case details for the error related to performance errors.

CodePudding user response：

Using an array, you're setting the "removed" elements as -1; repeatedly skipping them in each traversal causes the performance penalty.

Instead of an array, use a doubly linked list. Each removal can be easily done in O(1) time, and each left/right operation would only require shifting the current pointer by 2 nodes.

CodePudding user response：

As it already has been pointed outed both in the comments and the answer by @AbhinavMathur, in order to improve performance you need to implement Doubly linked list data structure.

Note that it's mandatory to create your own implementation that will maintain a reference to the current node. Attempt to utilize an implementation built-in in the JDK in place of the items array will not buy you anything because the advantage of the fast deletion will be nullified by the cost of iteration (in order to reach the element at position n, LinkedList needs to crawl through the n elements starting from the head, and this operation has a liner time complexity).

Methods left(), right() and position() will have the following outcome:

• left() - the previous node (denoted as prev in the code) associated with the current node will be dereferenced (i.e. current node would be associated with the previous node of the removed node and vice versa), and the current node would be assigned its new previous node. Time complexity O(1).

• right() - the next node (denoted as next in the code) associated with the current node will be dereferenced (i.e. current node would be associated with the next node of the removed node and vice versa), and the current node would be assigned its new next node. Time complexity O(1).

• position() - will return a value of the current node. Time complexity O(1).

That's how it might look like:

public class MyClass {
    private Node current; // instead of both position and items

    public MyClass(int n, int position) {
        Node current = new Node(0, null, null); // initialing the head node
        if (position == 0) {
            this.current = current;
        }
    
        for (int i = 1; i < n; i  ) { // initialing the rest past of the linked list
            Node nextNode = new Node(i, current, null);
            current.setNext(nextNode);
            current = nextNode;
        
            if (position == i) {
                this.current = current;
            }
        }
    }
    
    public void left() { // remove the node on the left and set current node to be a new previous node
        if (current.prev == null || current.prev.prev == null) {
            return;
        }
        
        Node newPrev = current.prev.prev;
        newPrev.setNext(current);
        current.setPrev(newPrev);
        this.current = newPrev;
    }

    public void right() { // remove the node on the right and set current node to be a new next node
        if (current.next == null || current.next.next == null) {
            return;
        }
    
        Node newNext = current.next.next;
        current.setNext(newNext);
        newNext.setPrev(current);
        this.current = newNext;
    }

    public int position() {
        return current.getValue();
    }
    
    public static class Node {
        private int value;
        private Node prev;
        private Node next;

        public Node(int value, Node prev, Node next) {
            this.value = value;
            this.prev = prev;
            this.next = next;
        }

        // getters and setters
    }
}