Arrays MCQs

In C++, an array is declared by specifying the type of elements followed by the array name and brackets with the size, e.g., int arr[5];

Arrays provide direct memory address calculation via base_address + index * element_size, which executes in constant O(1) time.

Contiguous memory means all elements are placed one after another in consecutive physical memory addresses.

C++ does not perform runtime bounds checking on native arrays for performance reasons, resulting in undefined behavior.

Most modern programming languages use zero-based indexing.

Kadane's algorithm calculates the maximum subarray sum in a single pass O(n) time.

Inserting at the beginning requires shifting all n existing elements one position to the right, taking O(n) time.

Static arrays cannot be resized. Dynamic resizing requires allocating a new memory block or using dynamic structures like std::vector.

Kadane algorithm only requires two variables (max_so_far and max_ending_here), utilizing O(1) auxiliary space.

The two-pointer technique places one pointer at the start and one at the end, converging in O(n) time on a sorted array.

In row-major order, entire rows are stored sequentially: row offset is i * C, plus column offset j.

Contiguous memory provides cache locality and direct address arithmetic for O(1) indexing.

A prefix sum array precomputes cumulative sums, allowing any subsegment sum arr[L...R] = pref[R] - pref[L-1] in O(1).

The Dutch National Flag algorithm partitions 0s, 1s, and 2s in a single pass with O(n) time.

Sliding window maintains a running calculation over a moving window of size k in O(n) time.

Most appends take O(1). The occasional O(n) reallocation is spread across all operations, yielding an amortized O(1) per insert.

Swapping elements from outer pairs inward takes n/2 operations, which is O(n) time.

Heap sort achieves guaranteed O(n log n) worst-case time complexity while operating in-place with O(1) extra space.

n*(n+1)/2 - sum(array) gives the missing number in O(n) time and O(1) space.

Total array size in bytes divided by size of a single element gives the number of elements in the static array.

A double-ended queue (deque) storing indices in decreasing order of values allows O(n) sliding window max.

Based on cycle decomposition of permutations, each cycle of length L requires L-1 swaps, with a maximum of n-1 swaps.

Boyer-Moore Voting algorithm maintains a candidate and count in O(n) time and O(1) space.

Java initializes primitive numeric array elements to 0 automatically.

Starting from the top-right corner allows pruning an entire row or column at each step, yielding O(R + C) time.