hackerrank Circular Array Rotation Python

Question

I tried to solve the Circular Array Rotation problem on HackerRank. https://www.hackerrank.com/challenges/circular-array-rotation/problem

The following code passes all test cases except case #4, which gets a runtime error. Could someone point out the problem?

def circularArrayRotation(a, k, queries):

    if k < len(a):
        k = k
    elif k == len(a):
        k = 0
    else:
        k = k%a

    newList = []


    for val in queries:
        newInd = -k+val
        if abs(newInd) > len(a):
            newInd = newInd - (len(a)-1)
            newList += [a[newInd]]
        else:
            newList += [a[newInd]]        


    return newList

you need to make it fast as it is exceeding the required time limit for that case — sahasrara62
– sahasrara62, Commented Jan 21, 2019 at 1:25
Try to get the rotated array at once and in new list store the value of that query index from rotated array — sahasrara62
– sahasrara62, Commented Jan 21, 2019 at 2:59

marc_s · Accepted Answer · 2019-01-21 15:13:24Z

4

Your solution is correct. But is not running within that time limit for that case 4 only.

You are calculating the value each time for new queries, which is taking time.

What you can do is take the rotated array at once . and then run the queries on the rotated array. Save the result in the list and return it back.

def circularArrayRotation(a, k, queries):

    new_arr = a[-k%len(a):] + a[:-k%len(a)]
    # list slicing is done here.  it will get the right rotated array 

    result = []
    for i in queries:
        result.append(new_arr[i])
        # running queries on rotated array
    return result

using above method , list slicing is done in o(n) time . and then running the queries is done is o(1) time.

edited Jan 21, 2019 at 15:13

marc_s

760k186 gold badges1.4k silver badges1.5k bronze badges

answered Jan 21, 2019 at 3:06

sahasrara62

11.4k3 gold badges35 silver badges48 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Tomerikoo · Accepted Answer · 2019-06-25 10:38:35Z

1

def circularArrayRotation(a, k, queries):
    j= len(a)

    for x in range(k):
        n=a[j-1]
        a.insert(0,n)
        a.pop(j)

    newList= []

    for m in queries:
        newList.append(a[m])

    return newList

edited Jun 25, 2019 at 10:38

Tomerikoo

19.6k16 gold badges57 silver badges68 bronze badges

answered Jun 25, 2019 at 10:27

shyamantha

771 silver badge8 bronze badges

Comments

Tomerikoo · Accepted Answer · 2021-05-31 09:38:07Z

1

def circularArrayRotation(a, k, queries):
    #rotation
    for _ in range(k):
        a.insert(0, a.pop())
    #putting answer according to query
    ans = []
    for i in queries:
        ans.append(a[i])    
    return ans

edited May 31, 2021 at 9:38

Tomerikoo

19.6k16 gold badges57 silver badges68 bronze badges

answered May 31, 2021 at 6:14

Hardik Shreyas

111 bronze badge

1 Comment

Thavas Antonio Over a year ago

While this code may answer the question, providing additional context regarding why and/or how this code answers the question improves its long-term value.

AnkushRasgon · Accepted Answer · 2019-06-25 10:48:19Z

0

Well you can use deque A deque is a double-ended queue. It can be used to add or remove elements from both ends.

from collections import deque
    def circularArrayRotation(a, k, queries):
        result=[]
        a = deque(a) 
        a.rotate(k) 
        a = list(a) 

        for v in queries:
            result.append(a[v])

        return(result)

answered Jun 25, 2019 at 10:48

AnkushRasgon

8301 gold badge8 silver badges15 bronze badges

Comments

Xgh05t · Accepted Answer · 2020-01-10 23:33:33Z

0

I know this is very old, but I was just solving this, so I figured might as well drop by, your else case is wrong! It should be k = k % len(a), you wrote k % a, now I write c++, so don't know what that even does in python, but I'm pretty sure that doesn't automatically put in len(a) Besides, why are you bothering putting that in if else block just modulo every time, if it's smaller, no value change, for => it fixes it to the right value.

answered Jan 10, 2020 at 23:33

Xgh05t

2403 silver badges11 bronze badges

Comments

Guillermo Abbona · Accepted Answer · 2020-07-23 15:07:42Z

0

I believe a deque is the approach to go, as AnkushRasgon's and shyamantha's answers. Here I post my version in Java. All tests passed.

static int[] circularArrayRotation(int[] a, int k, int[] queries) {

    LinkedList<Integer> list = Arrays.stream(a).boxed()
            .collect(Collectors.toCollection(LinkedList::new));
    
    for (int i = 0; i < k; i++) {
        list.push(list.pollLast());
    }
    
    for (int i = 0; i < queries.length; i++) {
        if (queries[i] < list.size()) {
            queries[i] = list.get(queries[i]);
        }
    }
    
    return queries;
}

answered Jul 23, 2020 at 15:07

Guillermo Abbona

434 bronze badges

Comments

pasan · Accepted Answer · 2020-08-20 17:35:23Z

0

def circularArrayRotation(a, k, queries):
    reverse_a = list(reversed(a))
    reverse_a_copy = reverse_a.copy()
    for x in range(k):
        item = reverse_a[x]
        reverse_a_copy.remove(item)
        reverse_a_copy.append(item)
    line = []
    for x in queries:
        line.append(list(reversed(reverse_a_copy))[x])
    return line

answered Aug 20, 2020 at 17:35

pasan

531 silver badge6 bronze badges

1 Comment

Brad Figueroa Over a year ago

You should always try to provide some explanation when you try to help someone solving a problem, it's much better and appreciated

Shyam Gupta · Accepted Answer · 2021-05-11 04:38:37Z

0

a=[1,2,3,4,5]
s=2
def rotateList(arr,d,n):
  arr[:]=arr[d-1:n]+arr[0:d-1]
  return arr

print(rotateList(a,5,len(a)))

answered May 11, 2021 at 4:38

Shyam Gupta

5194 silver badges8 bronze badges

Comments

shiva kumar · Accepted Answer · 2021-08-23 18:13:57Z

0

    for i in range(k):
        random_a = len(a)
        random_b = random_a - 1
        random_c = a.pop(random_b)
        a = [random_c] + a
    oz = a
    random_list = []
    for i in queries:
        z = oz[i]
        y = str(z)
        random_list.append(y)
    return random_list```
is this the correct answer

answered Aug 23, 2021 at 18:13

shiva kumar

1

1 Comment

Frank Over a year ago

Better to give an explanation of your answer.

Collectives™ on Stack Overflow

hackerrank Circular Array Rotation Python

9 Answers 9

Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

9 Answers 9

Comments

Comments

1 Comment

Comments

Comments

Comments

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related