Questions tagged [arrays]

A sequential random-access data structure whose size can typically not be changed after creation.

570 questions
Filter by
Sorted by
Tagged with
1 vote
2k views

Arrays. Find row with most 1's, in O(n)

Suppose that each row of an $n \times n$ array $A$ consists of 1's and 0's such that, in any row of $A$, all the 1's comes before any 0's in that row. Assume $A$ is already in memory, describe a ...
49 views

1 vote
87 views

Check if Two Arrays Sorted in Decreasing and Increasing Order Satisfy a Condition

Given 2 arrays $A, B$ each of size $n$. If we want to find if the two arrays satisfy the condition that $A[i] + B[i] \ge k$ for all indices $i$, it's sufficient to fulfill 3 conditions below: Sum of ...
• 505
47 views

Researching the complexity of a dynamic array with insert-last(x) and delete-last() operations

In this question I need your help researching time complexity of a dynamic array with insert-last(x) and delete-last() operations: We define a data structure and call it dynamic array, we define the ...
1 vote
654 views

Finding equal-sum subsets from two arrays

Consider the following problem: You are given two integer arrays $A$ and $B$ of size $N$ and $M$, respectively. You are guaranteed that $1 <= A[i] <= M$ and $1 <= B[i] <= N$ for all $i$ (...
275 views

How is a direct address table different from an array?

I found this from this PDF (https://web.stanford.edu/class/archive/cs/cs161/cs161.1168/lecture9.pdf)
• 161
74 views

Can contiguous arrays be lazily evaluated?

Contiguous arrays with variable length, such as C++'s std::vector, have been a major sequential container for languages whose evaluation is eager. However, it has ...
• 367
105 views

Speeding up an array search for duplicate

I was tasked with writing a function that finds the value of an element that is the first duplicate in an array to be encountered. For the array [2, 1, 3, 5, 3, 2] ...
• 101
202 views

Can somebody explain to me the concept of mutability with respect to a NumPy array?

From the NumPy documentation: "NumPy arrays have a fixed size at creation, unlike Python lists (which can grow dynamically). Changing the size of an ndarray will create a new array and delete ...
• 101
145 views

Algorithm to find minimum amount of swaps to convert array A into array B with repeated elements

I'm trying to create an algorithm that finds the minimum number of swaps to convert array A into array B. In this case the arrays can only contain the numbers 0, 1 or 2. So for example: given ...
• 25
1 vote
218 views

How do I find the most even combination for two arrays

I have two arrays that both contain $n$ elements (positive, non zero, not negative) $\{x_1\dots x_n\}$ $\{y_1\dots y_n\}$ I want to pair them up optimally, one from each array, so that the pairs come ...
1 vote
72 views

Finding the total work of an array list expansion effort

Suppose we are given an array-based list data structure. Suppose that its initial capacity is $m > 0.$ When appending an element to the end of the list, if the list is full, we extend its capacity ...
578 views

• 377
2k views

Why does the order of the nested loops matter when solving the Coin Change problem?

The Coin Change problem is stated as: Given an integer array coins[ ] of size N representing different denominations of currency and an integer sum, find the number of ways you can make sum by using ...
• 171
52 views

Is this an inversion problem?

I understand that total inversion in a sequence is the number of swaps that need to be done, to sort the sequence. And the best approach to solve this problem is to count swaps in a merge sort of the ...
124 views

Algorithm that finds 4 "O"s or 4 "X"s on a diagonal, horizontal, or vertical

My algorithm homework revolves around matching 4 "O"'s or 4 "X"'s on a diagonal, horizontal, or vertical. ...
• 123
39 views

Inversion array of a given array

Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i ...
1 vote
53 views

Are there adaptive algorithms/data structures for sparse and non sparse vectors?

A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value. A dense 1D array is commonly encoded as a linear array of values [value1, value2, ...
• 131
1 vote