Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [arrays]

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

1
vote
0answers
30 views

How to reduce number of move operations in an array?

Say I have an array of numbers, e.g. [0, 1, 2, 3, 4, 5] and I want to end up with an array, e.g. [2, 1, 4, 0, 5, 3]. At my ...
-2
votes
0answers
20 views

What is the answer to this arrays question? [on hold]

!((x > y) && (y <= 0)) is equivalent to which of the following expressions? !(x > y) && !(y <= 0) (x <= y) || (y > 0) (x < y) || (y > 0)
-4
votes
1answer
21 views

What is the answer to this problem? [on hold]

Suppose the following array is declared: int[ ] grades = {88, 92, 95, 83}; What are the values in grades after the following code executes? int temp = grades[0]; grades[0] = grades[1]; grades[1] = ...
0
votes
0answers
23 views

General algorithm to move a selected set of elements of an array to a new position in the same array [closed]

I have an array. I have to move 1 or more items (selected by the user), to a target user-given index in the same array. The selected items should be in the same relative order after the operation is ...
0
votes
1answer
36 views

How to compare an element with other elements within an array efficiently for a condition

I need to compare each index with one another and associated array value as well. For example, ...
-3
votes
0answers
9 views

PhoneBookDirectory array in java, explained in detail in picture below [closed]

The PhonebookEntry class exists and is working fine, so write the code as if you had it already.
0
votes
0answers
17 views

2D arrays in java [closed]

Forgive me if this is a stupid question, but I am a beginner in java and our teacher doesn explain it too well. I understand how to create a checkerboard in java. This is the code I am using. ...
2
votes
3answers
858 views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
-1
votes
1answer
34 views

Is there any way to find the nodes in the each subtree of each node having distance equal to height of the subtree?

We are given a tree of N nodes from 1 to N where node 1 is the root of the tree. For each node i from 1 to N, you have to find the numbers of nodes which are in the subtree of i and are at distance ...
1
vote
1answer
16 views

Why finding the difference between the adjacent elements of the array to find the maximum difference?

I want to understand a tricky method to find the maximum difference between two elements such that larger element appears after the smaller number. I found easy solution keeping track of the minimum ...
0
votes
1answer
41 views

The time complexity of finding the kth smallest number using buckets

I've implemented kth smallest number using buckets representing the current nibble value of each element in the array where ...
0
votes
1answer
42 views

Job scheduling approximation

In the course notes for Stanford MS&E-319: https://web.stanford.edu/class/msande319/lec1.pdf Lemma 5 is given as: The approximation factor of the modified greedy [scheduling] algorithm is 4/3....
0
votes
1answer
74 views

Partition array into k subsets

We are given an array and a number K. Partition array into K subsets such that let MaxSum be the maximum sum of among subsets. We have to minimize summation =$$\sum_{i=1}^{k}MaxSum-sum(i) $$ Is ...
6
votes
1answer
137 views

Sort 2D arrays so that cost of reaching new position as described at each iteration is minimized

Problem is as following: We are 8 trumpet players in an orchestra. There are for example 4 parts so there are always two players on the same part. Now, there are not always the same two players ...
3
votes
1answer
39 views

Using bit arrays to solve crossword puzzles

I have read Crossword Puzzles and Constraint Satisfaction by Connor, Duchi and Lo and I am trying to implement this variation of crossword solving algorithm. I can't understand the bit array data ...
7
votes
2answers
461 views

Find a point shared by maximum segments

Given: $N$ segments (arrays) of ordered integers, integers could be from $-K$ to $K$. Example: ...
4
votes
1answer
96 views

Maximum subarray of bounded length

I'm giving an array $A[0..n-1]$ and an integer $w$. The goal is to find indices $i,j$ that maximize $$\Phi(i,j) = A[i] + A[i+1] + \dots + A[j-1],$$ subject to the requirements that $0 \le i \le j \...
59
votes
3answers
10k views

In-place algorithm for interleaving an array

You are given an array of $2n$ elements $$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$ The task is to interleave the array, using an in-place algorithm such that the resulting array looks like $$...
0
votes
4answers
6k views

Partition array into K subsets, each with balanced sum

Given array $A = \{ a_{1},a_{2}, ..., a_{n}\}$ and integer $k; 0 \lt k \le n$, partition array $A$ into $k$ subarrays, such that $A'_{1} = \{a_{1}, ...,a_{x}\}$ $A'_{2} = \{a_{x+1},...,a_{y}\}$ $......
2
votes
0answers
42 views

Minimum number of deleting palindromes to delete whole string

Let's say we have given array $A$ of size $n$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only ...
3
votes
1answer
30 views

Finding maximum takes at least $\lceil n/2 \rceil$ comparisons

We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$. I want to prove that finding the maximum in $A$ (that is, outputting the index ...
-2
votes
1answer
91 views

Count the number of subsets with product less than or equal to k [closed]

You are given an array $A$ of $n$ positive integers, you have to find the number of subsets the product of whose elements is less than or equal to a given integer $k$. Is there an efficient algorithm ...
2
votes
0answers
57 views

Min no.of operations required to convert an array to which it should contain elements of equal frequency

I have come across this tricky problem. An array of N elements should be converted to another array within k operations such ...
3
votes
1answer
50 views

Efficient algorithm to replace list of integers with nearest bigger element

The original question was in the context of an array, but I just used a list without changing the length for easier debugging purposes of toString(). Given an ...
2
votes
1answer
120 views

Time complexity to find Median of Medians

I recently wrote my Grad school Admission test few days back and the following question appeared in the test. There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ....
2
votes
2answers
148 views

Finding the maximum of a bitonic sequence

Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] &...
0
votes
1answer
32 views

Algorithm to generate repetitive sequence of fixed length

I am trying to create an algorithm to generate test cases. Each test case is an array of $n$ natural integers which are randomly generated using a pseudo-random function. The bound for $n$ is $0 < ...
0
votes
1answer
51 views

Applying minimax tree to this array [closed]

Please tell me how I should apply minimax algorithm to the array $$ 15, 12, 14, 16, 11, 13$$ and make a tree?(I understand how minimax algorithm works but I can't apply it to an array)
32
votes
4answers
2k views

How to measure “sortedness”

I'm wondering if there is a standard way of measuring the "sortedness" of an array? Would an array which has the median number of possible inversions be considered maximally unsorted? By that I mean ...
2
votes
1answer
84 views

How to find efficiently the minimum modification to avoid close consecutive numbers?

I have an array of sorted numbers: arr = [-0.1, 0.0, 0.5, 0.8, 1.2] I want the difference (dist below) between consecutive ...
1
vote
2answers
98 views

FInding the combination with the least number of elements from and array of integers, given an integer sum

I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
0answers
26 views

Recurrence Relation for Column Major Form of multidimensional array

A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence $$A[0][0] A[1][0] A[2][0]...A[n_1-1][0] ... A[0][1] A[1][1] ... A[n_1-1][1] .... A[...
1
vote
2answers
64 views

What does the “0 ≤ K < N-1” expression means?

Given the following statement: "A nonempty array A consisting of N integers is given. Any integer K, such that 0 ≤ K < N-1, splits array A into two non-empty parts" What does the 0 ≤ K < ...
3
votes
2answers
72 views

Is it possible to solve this problem in less than n^2 time without using additional space?

Here's the problem: Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range ...
2
votes
1answer
40 views

Find four sets where each element from those four appears in at least two of those four sets

I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array: $A_i = \{x_{i,1}..x_{i,c_i}\}$ $x_{i,p} < x_{i,p+1}$ $A_i$ ...
1
vote
2answers
22 views

Generate Evenly Distributed Pattern Based on Weights

I have an array of items $A = \{A_i\}, i \in I $ with integer weights $W_i, i \in I$. I need to build a function $f: I \rightarrow A $, that produces evenly distributed patterns of array elements ...
1
vote
0answers
135 views

Array subset division with equal sums

Today I stumbled upon a problem which looked like the partition problem but certainly is different. Given array of positive integers, guaranteed to not be divisible into two continious subsets of ...
3
votes
1answer
89 views

Find the smallest element greater than current element

my question is that given a list of integers (lets say A), for each element A[i], find the smallest element A[j] which could satisfy A[i] < A[j] and i < j. Return -1 if there is no such element. ...
0
votes
1answer
19 views

How to count stores in cache analysis of matrix multiplication

I'm trying to understand cache misses/iter and came across this that I couldn't understand or reason out. For ijk iteration, my slides say that there are 2 loads and 0 stores. ...
6
votes
2answers
173 views

Transforming an array into one with descending order

Problem Description Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) descending order: we require that $\hat{a}_i \...
1
vote
0answers
71 views

How does prefix summing the count histogram in counting sort result in an array of output indices?

My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is: ...
0
votes
1answer
114 views

Is my algorithm a $O(nm \lg m)$ solution for sorting a row and columnwise sorted $2D$ array?

The problem (from MIT 6.006 course) is the following: In this problem, you are given a $2D$ array of integers $A$ that has $n$ rows and $m$ columns. (Assume $m$ is much (e.g., exponentially) ...
1
vote
1answer
28 views

How would you identify the size of a circular turing tape?

Came across this interesting problem in one of my interviews. Suppose you have a circular turing tape, i.e. simply a circular array. You do not know the size i.e. the number of cells available in that ...
2
votes
0answers
60 views

Sort arrays $A$ and $B$ of the same elements using only comparisons between an element of $A$ and one of $B$

Premise: Let $A := [ k(1), k(2), ..., k(n) ]$ and $B:=[ l(1), l(2), ..., l(n) ]$ be two Arrays where $k$ and $l$ are permutations. (What I'm trying to express: $A$ and $B$ contain the same elements in ...
2
votes
1answer
103 views

Maximum number of segments with no intersection [duplicate]

This is an interview question. Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
0
votes
1answer
41 views
4
votes
3answers
105 views

Sum of unique elements in all sub-arrays of an array

Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$. Subarrays: ...
0
votes
1answer
40 views

Strengths and limitations of arrays [closed]

What are the strengths and limitations of arrays? What considerations go into choosing an array over another data structure, or vice-versa?