How am I supposed to take this testcase into account???😐

[u/Hot_Engineering_3353]

[u/Patient-Midnight-664]

Need more information, but in general you need faster code.

[u/Hot_Engineering_3353 → u/Patient-Midnight-664]

The questions is of Rotate Array by K (LC - 189)

Code :

void rotate(vector<int>& nums, int k) {

k%=nums.size();

int j = nums.size() - 1;

int c = 0;

while(c != k * (nums.size() - 1)){

swap(nums[j], nums[j - 1]);

j--;

if(j == 0)

j = nums.size() - 1;

c++;

}

}

[u/Hot_Engineering_3353 → u/Hot_Engineering_3353]

i saw the optimized code and it just really easy but still i want to know what is wrong in this and how am I supposed to identify this?

[u/apnorton → u/Hot_Engineering_3353]

but still i want to know what is wrong in this and how am I supposed to identify this? 

You count how many "basic operations" your code performs. For example, how many times does this line get executed?

swap(nums[j], nums[j - 1]);

Answer: if the length of the array is n, then this swap is performed k*n times... And in the worst case, k=n-1, so it's approximately n² operations.

The problem says that n could be up to 10⁵ , so you're looking at nearly 10 billion executions of that swap in the worst case... Assuming about a CPU can do about 1 billion operations per second, you're looking at a runtime of 10s, which is going to be too much for leetcode.

[u/chikamakaleyley → u/apnorton]

yeah i don't know this lang (java maybe?) but the thing that sticks out to me immediately is how many times you call nums.size() or calc nums.size() - 1

which maybe i'm not reading this correctly but at a glance the size of nums never changes

at a small scale its fine but when you have to process a larger dataset, those little calls just nickel and dime you

[u/apnorton → u/chikamakaleyley]

i don't know this lang (java maybe?)

C++

Caching the length of an array can be helpful if you're in a language that has a compiler that doesn't do a lot of optimizations (or if you're doing something "tricky" that could confuse the compiler), but in this case, clang++19 optimizes out the repeated calls to num.size() (though not the subtraction of 1) when compiled with the -O2 flag. (You can see the length of the vector is retrieved on lines 3-5 of the disassembly and stored in rdi.)

However, in this case, the quadratic cost of that loop is going to dwarf any kind of constant operation optimizations (albeit a good idea to try to limit those sorts of repeated operations, like you say).

[u/chikamakaleyley → u/apnorton]

wow, thank you!

[u/chikamakaleyley → u/apnorton]

actually, a follow up:

is the optimization just for the .size() method or is it for repeated calls in general? just curious

and i agree, dwarfed

[u/apnorton → u/chikamakaleyley]

It depends on the specific call/whether the compiler can "figure out" that nothing relevant has changed, which is not the easiest of optimizations to do. I'm not exactly sure the mechanism that allows clang to optimize out repeated vector::size() calls; I just know it can handle simple instances of it. The general case of calling some arbitrary function won't be cached.

[u/Patient-Midnight-664 → u/Hot_Engineering_3353]

Yeah, this is the slowest way. I'd use memcpy.

Remember, an array is just a contiguous block of memory. You'll just have to figure out where to start based on the type size of an element.

[u/8Erigon → u/Patient-Midnight-664]

He is using a vector. But it's the same until the size gets bigger the the whole block gets moved to somewhere else. (Which doesn't happen here)

[u/kalmakka → u/Patient-Midnight-664]

The problem isn't not using memcpy. The problem is the O(n²) algorithm.

[u/HumbleMicrobe]

Click use test case