Moving character efficiently on a row

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 the input is large.

How to implement this efficiently? I don’t have test case details for the error related to performance errors.

Answer

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() – in case when the previous node (denoted as prev in the code) associated with current is not null, and in tern its previous node exists, the current node will be dereferenced (i.e. next and previous nodes associated with the current node will be linked with each other), and the variable current would be assigned to the prev of the previous node, i.e. current.prev.prev. Time complexity O(1).

• right() – in case when the next node (denoted as next in the code) associated with current is not null, and in tern its next node exists, the current node will be dereferenced in a way that has been described above, and the variable current would be assigned to the next of the next node, i.e. current.next.next. 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; // a replacement for both position and items fields

    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() { // removes the current node and sets the current to the node 2 position to the left (`prev` of the `prev` node)
        if (current.prev == null || current.prev.prev == null) {
            return;
        }
        
        Node prev = current.prev;
        Node next = current.next;
        prev.setNext(next);
        next.setPrev(prev);
        this.current = prev.prev;
    }

    public void right() { // removes the current node and sets the current to the node 2 position to the right (`next` of the `next` node)
        if (current.next == null || current.next.next == null) {
            return;
        }

        Node prev = current.prev;
        Node next = current.next;
        prev.setNext(next);
        next.setPrev(prev);
        this.current = next.next;
    }

    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
    }
}

A link to Online Demo