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.

## Advertisement

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

**6**People found this is helpful