Skip to main content

Questions tagged [arrays]

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

Filter by
Sorted by
Tagged with
1 vote
2 answers
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 ...
Science Guy's user avatar
2 votes
3 answers
49 views

Prove that the L1 distance between two arrays is minimized when both are sorted

Suppose you are given two arrays of the same length $n$, say $a$ and $b$ containing unique positive integers. The L1 distance between $a$ and $b$ is defined as: $$d_1(a, b) = \sum_{i = 1}^n \lvert a_i ...
kaddy's user avatar
  • 83
1 vote
1 answer
57 views

Algorithm to sort array into K increasing subsets?

Let's say we got an array of size n with real numbers, and a natural number k. n must be multiple of k. We want to sort the array in a way that, when we divide this array into k subsets of equal size, ...
user166586's user avatar
1 vote
1 answer
134 views

Finding the smallest root

We are given an array $a$ of $n$ integers, such that the difference between each element $a[i]$ and the adjacent elements $a[i-1]$ and $a[i+1]$ is at most $1$. Define a root of $a$ as an index $k$ in $...
Erel Segal-Halevi's user avatar
1 vote
1 answer
38 views

Will CSR format store the all 0 column?

In the matrix(3 rows and 7 columns) below with 4 all zero columns 0 4 0 0 0 0 0 2 1 0 0 0 0 0 0 0 3 0 0 0 0 The CSR format of storage is : row_ptr: [0, 1, 3, 4] col_ind: [0, 0, 1, 2] values: [4, 2, ...
san zhang's user avatar
1 vote
1 answer
88 views

Loop Bounds vs. Iteration Domain in Polyhedral optimization

Context: I was reading a tutorial on polyhedral optimization. But got confused while trying to translate the iteration domain (i.e. loop bound) to set builder notation. Problem Description: A code ...
F.C. Akhi's user avatar
  • 123
4 votes
3 answers
106 views

Element that occurs more than one third of the time in a sorted array - constant time?

Given a sorted array of positive integers that is guaranteed to have some unique entry that occupies more than $1/3$ of the entries, is there an algorithm to determine this entry in $O(1)$ time? Some ...
user165069's user avatar
0 votes
0 answers
13 views

Flowgarithm for common child program for a beginner (without pointers)

I'm a first year BCA student. Can you help me with flowgarithm of the common child problem (LCS) without pointers
Anandhakrishnan's user avatar
1 vote
0 answers
40 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
67 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
123 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
  • 13
0 votes
1 answer
92 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
33 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: ...
Dracula's user avatar
  • 103
1 vote
2 answers
103 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
  • 208
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
13 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
  • 493
2 votes
1 answer
125 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
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 ...
Avv's user avatar
  • 505
0 votes
0 answers
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 ...
T-Caster's user avatar
1 vote
1 answer
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$ (...
Christopher Miller's user avatar
0 votes
3 answers
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)
Neel Sandell's user avatar
0 votes
1 answer
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 ...
Dannyu NDos's user avatar
0 votes
2 answers
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] ...
Lucky's user avatar
  • 101
0 votes
1 answer
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 ...
NaiveBae's user avatar
  • 101
0 votes
1 answer
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 ...
Tomyy's user avatar
  • 25
1 vote
2 answers
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 ...
Ally Zane's user avatar
1 vote
0 answers
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 ...
coderodde's user avatar
-1 votes
2 answers
578 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
191 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
119 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
25 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
494 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
114 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
160 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
417 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
3 votes
2 answers
193 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
183 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
737 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
797 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
  • 355
0 votes
3 answers
139 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
277 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
57 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
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 ...
Ogunleye Ayowale Pius's user avatar
2 votes
4 answers
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. ...
bbartling's user avatar
  • 123
-2 votes
1 answer
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 ...
user11058024's user avatar
1 vote
1 answer
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, ...
Colim's user avatar
  • 131
1 vote
1 answer
76 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 ...
harshmangalamv's user avatar
0 votes
0 answers
50 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

1
2 3 4 5
12