Java solution Using Queue


  • 0
    S

    The idea of this solution is to use a custom queue data structure that will be used to rotate the array. The original array is put into the queue, the rotation function is calculated and then the last element from the queue is taken from the tail and put in the front of the queue. Then the rotation function is calculated again. This algorithm repeats n times. The code is as follows:

    class Solution {
        
        private static class Queue {
            public static class Node {
                int val;
                Node below;
                
                public Node(int val, Node below) {
                    this.val = val;
                    this.below = below;
                }
            }
            
            Node head;
            Node tail;
            int size = 0;
            
            public Queue(int[] A) {
                for(int x : A) {
                    add(x);
                }
            }
            
            public void add(int val) {
                Node n = new Node(val, tail);
                if (head == null && tail == null) {
                    head = n;
                    tail = head;
                } else {
                    tail = n;
                }
                size++;
            }
            
            public Node pop() { 
                Node n = tail;
                tail = tail.below;
                n.below = null;
                size--;
                return n;
            }
            
            public void pushHead(Node n) {
                head.below = n;
                head = head.below;
                size++;
            }
            
            public void rotate() {
                pushHead(pop());
            }
            
            public int getRotation() {
                Node n = tail;
                int sum = 0;
                for (int i = size - 1; i >= 0; i--) {
                    sum += i * n.val;
                    n = n.below;
                }
                
                return sum;
            }
        }
        
        public static int maxRotateFunction(int[] A) {
            if (A.length == 0 || A == null) {
        		return 0;
        	}
        		
            Queue q = new Queue(A);
            int max = Integer.MIN_VALUE;
            for (int i = 0; i < A.length; i++) {
                int curr = q.getRotation();
                if (max < curr) {
                    max = curr;
                }
                
                q.rotate();
            }
            
            return max;
        }
    }
    

    Every node in the queue has a link to the one before it. When we want to calculate the rotation function we start from the tail is we only have a link to the element before, not after. In this case it is handy to keep track of the size of the queue.


Log in to reply
 

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