Questions tagged [arrays]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
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 ...
HelpmePlease's user avatar
0 votes
0 answers
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 ...
Connor's user avatar
  • 101
1 vote
1 answer
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 ...
Lorenzo's user avatar
  • 11
0 votes
1 answer
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$....
coderodde's user avatar
0 votes
0 answers
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: ...
Parth's user avatar
  • 103
1 vote
2 answers
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: ...
tbhaxor's user avatar
  • 128
0 votes
0 answers
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 ...
lesobrod's user avatar
  • 111
0 votes
0 answers
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 ...
porton's user avatar
  • 433
2 votes
1 answer
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\}|.$$ ...
Vladislav Bezhentsev's user avatar
1 vote
1 answer
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 ...
Avv's user avatar
  • 493
0 votes
0 answers
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 ...
T-Caster's user avatar
1 vote
1 answer
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$ (...
Christopher Miller's user avatar
0 votes
0 answers
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): ...
BlueInundation's user avatar
0 votes
3 answers
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)
Neel Sandell's user avatar
0 votes
1 answer
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 ...
Dannyu NDos's user avatar
0 votes
2 answers
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] ...
Lucky's user avatar
  • 101
0 votes
1 answer
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 ...
NaiveBae's user avatar
  • 101
0 votes
1 answer
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 ...
Tomyy's user avatar
  • 25
1 vote
2 answers
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 ...
Ally Zane's user avatar
1 vote
0 answers
71 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 ...
coderodde's user avatar
-1 votes
2 answers
277 views

Local minimum in array, find $O(\log n)$ algorithm

Main Problem Given an array $A[1...n]$ ($n \geq 3$) of distinct integers with at least a local minimum, output a local minimum. A local minimum is an integer $1 < i < n$ such that $A[i-1] > A[...
almanfu's user avatar
0 votes
0 answers
53 views

Is this minimizing problem NP-hard?

We have $c$ arrays of positive integers, named $j[1],j[2],j[3]..,j[c]$. We know that the length of $j[i]$ is $c-i+1$. In addition, the sum of the numbers of $j[i]$ is greater than or equal to the sum ...
Soroush Vahidi's user avatar
4 votes
1 answer
174 views

Possibly Tractable Variation of Suguru Puzzles

I'm currently investigating the computational complexity of a modified one-dimensional Suguru puzzle. The general Suguru puzzles were recently proven to be NP-complete (see here). My investigation ...
Inteurce's user avatar
1 vote
2 answers
84 views

Division by zero in APL: assign return value 0 or 1

Recently I began learning a couple array based programming languages: Dyalog APL and BQN. And I cam across this peculiar manner in which division by zero is handled in Dyalog APL. Using the in-built ...
oliverjones's user avatar
0 votes
0 answers
23 views

Succinct array datastracture

Is it true that there is no known succinct data structure that has integer array (vector) functionality? Desirable operations would be: append O(1) access(i) - returns i-th item O(1) iterate(i..j) - ...
mcmayer's user avatar
  • 141
-2 votes
2 answers
264 views

Modified Bubble Sort's time complexity

I have an array (of hundreds of numbers) and I need to sort them. In this case, I used Bubble Sort because of the better time complexity compared to other algorithms, $\Theta(n^2)$. ...
Festona's user avatar
-2 votes
1 answer
65 views

Is there an algorithm that can get the minimal element of a min-heap in O(log* n)?

I came across this question when studying for an exam: given a min-heap that has no prime numbers in it, is there an algorithm that can get and delete the minimum of that heap in O(log* n) ? The ...
Alina's user avatar
  • 1
0 votes
2 answers
143 views

Can you help me in finding an algorithm that finds the first unique number in an array with lowest position?

I have the following problem to solve: Given a non-empty array A consisting of N integers, the task is to find the first unique number in the array. A unique number is defined as a number that occurs ...
Ardita Morina's user avatar
-1 votes
2 answers
388 views

Longest increasing subsequence when a number can be added to all numbers in a subarray

A sequence $(a_1,a_2, \dots, a_n) $ and natural numbers $n$ and $k$ are given. We want to calculate the longest (strictly) increasing subsequence of sequence $(b_1,b_2, \dots, b_n)$ for which there ...
Hjm's user avatar
  • 47
2 votes
2 answers
140 views

Producing "moves" to permute one array to another

I have 2 arrays, A and B, which each contain the same N elements, but in a different order. (A different permutation) There are also no duplicates in A and B. I'm trying to devise an algorithm which ...
123veggie123's user avatar
1 vote
2 answers
95 views

Convert lower-left matrix triangle 1D index to row, column

How can I convert a 1D index in the lower-left triangle of a grid into a row and column? For example, consider this table of 1D indices, indexed by row and column ...
Andy Thomas's user avatar
0 votes
1 answer
349 views

Finding majority element in $\mathcal{O}(nlogn)$ time

I am trying to build the logic behind a divide and conquer algorithm that will find the majority element in a matrix $A$ with $n$ elements in $\mathcal{O}(nlogn)$ time. I thought that in order to make ...
Tita's user avatar
  • 225
1 vote
1 answer
675 views

Minimal number of positive intervals to cover all positive elements

I'm struggling in finding a correct way to approach this, I'm aware that this problem is solvable using dynamic programming, and this problem somehow relates to the "max non-contiguous subarray&...
Aishgadol's user avatar
  • 315
0 votes
3 answers
136 views

is there an O(n^2) approach to this problem?

Given an array of N elements, I need to split it into k subarrays, where k can be between 2 <= k <= N. A sub-array's score is determined by: (left boundary point - right boundary point of the ...
stillmute's user avatar
0 votes
1 answer
121 views

Finding number of combinations of numbers from multiple arrays that add up to a given value

Let $ A $ be an array of $ n $ integer arrays with unknown lengths and $ s \in \mathbb{Z} $ a given number. I want to find the number of combinations of numbers from each array, such that their sum ...
talopl's user avatar
  • 101
0 votes
1 answer
42 views

Construct an objective function that favors the sorted permutation

I was looking into complexity theory and disappointed by the fact that a problem as simple as sorting an array isn't in the class $P$. This is because the class is defined only for decision problems (...
Rohit Pandey's user avatar
6 votes
2 answers
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 ...
Elad Maimoni's user avatar
0 votes
1 answer
49 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 ...
Ogunleye Ayowale Pius's user avatar
2 votes
4 answers
114 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. ...
bbartling's user avatar
  • 123
-2 votes
1 answer
36 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 ...
user11058024's user avatar
1 vote
1 answer
50 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, ...
Colim's user avatar
  • 131
1 vote
1 answer
72 views

Unable to understand how the while loop extracts the least number of coins with given sum

I was reading this classical Coin Problem (7.1): Given a set of coin values coins = {c1, c2,..., ck} and a target sum of money n, our task is to form the sum n using as few coins as possible. I fully ...
enerneo's user avatar
  • 13
0 votes
0 answers
39 views

Display XY data on computer

I would like to experiment with displaying the output of an analog to digital converter on computer. Samples of the ADC output would determine the intensity of one pixel. The input to the ADC is an ...
Otto Hunt's user avatar
25 votes
3 answers
3k views

Array access is O(1) implies a fixed index size, which implies O(1) array traversal?

Arrays are generally presented as data structures with $\Theta(N)$ traversal and $\Theta(1)$ random element access. However, this seems inconsistent: if array access is really $\Theta(1)$, this means ...
Antoine Pietri's user avatar
-1 votes
2 answers
356 views

Minimum absolute sum of 2 elements from 2 different lists

I am currently stuck on this problem, it is from a very highly competitive contest and so it is highly difficult as well. Below is the statement: ...
Minh Đức Hoàng's user avatar
0 votes
2 answers
77 views

Finding an element within an array that satisfies some rule

I saw a question on an old exam in my university course of DSA and I am not sure if the question is far too easy or if I am missing something. The question is : Given an array A that consists of N ...
Yarin's user avatar
  • 229
1 vote
0 answers
172 views

Minimum swaps to rearrange array so that the same numbers are in consecutive positions

Problem: Given an array of $N$ integers in range $[1,M]$, count the minimum number of swaps to rearrange array such that the same values are in a row. For example, given an array $[1,2,1,1,2,1,2]$. ...
GAVD's user avatar
  • 159
0 votes
2 answers
363 views

Why do the pointers in Two-pointer algorithm move only towards each other?

Problem statement- Given a sorted array, print out the pair of elements of the array that have a sum of K, where K is a whole number. The solution to the above problem goes like this: With using the ...
skekmal's user avatar
2 votes
2 answers
841 views

How can I apply binary search to find two adjacent increasing elements in an unsorted array?

I need to write a function that gets an array of numbers $a$ as an input and returns an index $i$ such that $a[i]<a[i+1]$ if it exists, if such $i$ doesn't exist return $-1$. (return any index $i$ ...
Pwaol's user avatar
  • 164
0 votes
2 answers
3k views

Maximum subarray sum of given length range

Can anyone please help me solve this better than $O(|a-b| \cdot n)$? Given an array of both negative and positive numbers, we want to find the maximum sum of the elements in contiguous subarray having ...
Iris's user avatar
  • 53

1
2 3 4 5
12