Between iterations of the same loop, are local variables reused or reallocated?

I always understood that defining a local variable within a loop does not slow it down because they are reused between iterations of the same loop.

I was surprised to find that when I move the definition of the local variable outside the loop, then it reduces memory significantly (39.4Mb vs 40 Mb).

Between iterations of the same loop, are local variables reused or reallocated?

I did also see https://stackoverflow.com/questions/51394012/allocation-of-space-for-local-variables-in-loops

> Duplicate Zeroes Problem (leetcode): Given a fixed length array arr of integers, duplicate each occurrence
> of zero, shifting the remaining elements to the right.
>
> Note that elements beyond the length of the original array are not
> written.
>
> Do the above modifications to the input array in place, do not return
> anything from your function.

import java.util.Arrays;

/**
 * algorithm: the zeroes divide the array into sub-arrays or subsets.
 * we move or shift the elements exactly once, to their final resting place R.I.P. ;)
 * The last subset will be shifted n0s places, the one before it, n0s -1 places and so on...
 * O(n)
 * @author likejudo
 *
 */
public class DuplicateZeroes {
	static void arrayCopy(int[] arr, int begin, int end, int n) {
		for (int i = end + 1; i >= begin ; i--) {
			int destination = i + n;
			if (destination < arr.length) {
				arr[destination] = arr[i];
			}
		}
	}

	public static void duplicateZeros(int[] arr) {
		int n0s = 0; // number of zeroes
		int last0At = -1; // last zero at index
		int boundary = 0; // rightmost boundary

		// find total n0s, last0At
		for (int i = 0; i < arr.length; i++) {
			if (arr[i] == 0) {
				n0s++;
				last0At = i;
			}
		}
//		System.out.format("n0s=%d last0At=%d \n", n0s, last0At);

		// if no zeroes or all zeroes, we are done
		if(n0s == 0 || n0s == arr.length) {
			return;
		}
		
		boundary = arr.length - n0s;

		while (n0s > 0) {
		//	System.out.format("before arrayCopy(%s, %d, %d, %d) ", Arrays.toString(arr), last0At, boundary, n0s);
			// move subset of all elements from last0At till boundary-1, by n0s spaces.
			arrayCopy(arr, last0At, boundary, n0s);
			// set start of subset to 0
			arr[last0At] = 0;
//			System.out.format("after arrayCopy : %s assigned arr[last0At=%d]=0\n", Arrays.toString(arr),last0At);
			// update boundary
			boundary = last0At - 1;
			// next subset to the left will have one less zero
			n0s--;
			last0At--;

			// find the next last zer0 At index
			while (last0At > 0 && arr[last0At] != 0)
				last0At--;
			// if no more...
			if (last0At <0 || arr[last0At] != 0) {
				return;
			}
		}
	}

	public static void main(String[] args) {
		// input: [1, 0, 2, 3, 0, 4, 5, 0]
		// output: [1, 0, 0, 2, 3, 0, 0, 4]

		int[] arr = {0,0,0,0,0,0,0};
		System.out.println("input:  " + Arrays.toString(arr));

		duplicateZeros(arr);
		System.out.println("output: " + Arrays.toString(arr));

	}

}

In the method arrayCopy, when I move the local variable destination outside the loop,

Before

	static void arrayCopy(int[] arr, int begin, int end, int n) {
		for (int i = end + 1; i >= begin ; i--) {
			int destination = i + n; // >>>>>>>>>>>>>>>>>>>>>>>
			if (destination < arr.length) {
				arr[destination] = arr[i];
			}
		}
	}

After

memory usage improved! (39.4 Mb vs 40 Mb)

static void arrayCopy(int[] arr, int begin, int end, int n) {
    int destination = 0; // >>>>>>>>>>>>>>>>>
	for (int i = end + 1; i >= begin ; i--) {
		destination = i + n;
		if (destination < arr.length) {
			arr[destination] = arr[i];
		}
	}
}

About your question

> I always understood that defining a local variable within a loop does
> not slow it down because they are reused between iterations of the
> same loop.
>
> declaring local variable inside loop does not slow it down?

• Yes, you are right. Declaring local vars does not increase the time complexity, or if it does change the runtime just a bit, it's too insignificant to be considered.

• Runtime and memory measurements of LeetCode are highly inaccurate, especially runtime. For instance, I just resubmitted the following solution and it says 39.6 MB, some days ago said 43.3 MB for the exact same solution without a byte change:

• Their test cases are usually limited because it is costly I guess, thus their benchmarking is not valuable.

public final class Solution {
    public static final void duplicateZeros(int[] arr) {
        int countZero = 0;

        for (int index = 0; index < arr.length; index++)
            if (arr[index] == 0) {
                countZero++;
            }

        int length = arr.length + countZero;

        for (int indexA = arr.length - 1, indexB = length - 1; indexA < indexB; indexA--, indexB--)
            if (arr[indexA] != 0) {
                if (indexB < arr.length) {
                    arr[indexB] = arr[indexA];
                }

            } else {
                if (indexB < arr.length) {
                    arr[indexB] = arr[indexA];
                }

                indexB--;

                if (indexB < arr.length) {
                    arr[indexB] = arr[indexA];
                }
            }
    }
}

• Overall it'd be best to focus on asymptotically efficient algorithms mostly, because benchmarking has lots of "how-tos" and we'd want to have really good resources (CPU, memory, etc.) with isolated test systems.

References

• For additional details, please see the Discussion Board where you can find plenty of well-explained accepted solutions with a variety of languages including low-complexity algorithms and asymptotic runtime/memory analysis^{1, 2}.