# Questions tagged [arrays]

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

564 questions
Filter by
Sorted by
Tagged with
31 views

### How do i make a 2d array as same as i possibly can with another one?

Say i have an 2d array A of nxn size, int values already given for each item.these values can be the same or different. There's gonna be another nxn array B being input. I can only interchange one row ...
12 views

### How do you understand Systolic Arrays?

I'm working on a problem from the Digital Design and Computer Architecture course on Systolic arrays. The question set up is as follows: The following diagram is a systolic array that performs the ...
1 vote
63 views

### Sorting rational numbers in linear time

I am currently studying algorithms and computational complexity at University. I have recently got through three questions I found in an old exam: Is it possible to sort in asymptotically linear time ...
49 views

### Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time

Suppose I have a dynamic table supporting $Insert$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $q > 1$....
24 views

### Finding minimum in a descending rotated sorted array with duplicates

For this question (154. Find Minimum in Rotated Sorted Array II ), I have a solution: ...
1 vote
64 views

### Why is 3[arr] notation of accessing elements in array is not used?

Today, I came across the notation 3[arr] in C++, and I was surprised to find out that it's a valid way to access array elements. For example: ...
14 views

### Periodicity of substitution system

I’m interested in substitution systems: maps which use a set of rules to transform elements of a sequence into a new sequence. For simplicity we will consider here only binary 1-D arrays. Unlike the ...
11 views

### Keeping in a list a list of recent insertions/removal to/from a list of lists

I have a list of lists T. I stress test my database software by randomly adding and removing sublists and elements of sublists to/from T and from/to my database. (After this I compare T with the ...
102 views

### Data structure for querying maximum of a rolling total

Let $A = \{a_1, \ldots, a_n\}$ be a set of numbers and $w$ be some number. Define $p_w^{A}: \mathbb{R} \rightarrow \mathbb{N}$ as $$p_w^{A}(r) = |\{i \in \{1, \ldots, n\} | r \leq a_i \leq r + w\}|.$$ ...
1 vote
63 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 ...
38 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
347 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$ (...
14 views

### Finding a ArrayList Connection (representing Subway Lines) with Recursion

I have this ArrayList (called linArray) (and this only) that contains Subway exchange stations (first the station name and then the lines you can exchange to at that station): ...
114 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)
67 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 ...
75 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] ...
97 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 ...
74 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 ...
1 vote
128 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
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 ...