# Questions tagged [complexity]

Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.

343 questions
Filter by
Sorted by
Tagged with
2k views

### Return the anti-diagonals

Give a N*N square matrix, return an array of its anti-diagonals. Look at the example for more details. Example: Input: ...
1k views

### Find The Duplicates in two arrays

Find The Duplicates Given two sorted arrays arr1 and arr2 of passport numbers, implement a function findDuplicates that returns an array of all passport numbers that are both in arr1 and arr2. Note ...
334 views

### Space complexity of the “add two binary strings” challenge

I was solving this problem of "adding two string binary numbers" and came up with the following algorithm. I am trying to analyze its time and space complexity. While I was satisfied with its time ...
117 views

### Finding duplicates in arrays

I'm given two sorted arrays, arr1 and arr2. They can either be of the same length or arr2 ...
205 views

### Finding the number of ways to partition {1,2, …, N} into p1 and p2 such that sum(p1) == sum(p2)

I am trying to write a space and time efficient algorithm to calculate the number of ways to partition a set of integers {1, 2, ..., N} into two partitions such that the sums of integers in the two ...
625 views

### Genomic Range Query in Python

Recently, I worked on one of the Codility Training - Genomic Range Query (please refer to one of the evaluation report for the detail of the task. The solution in Python is based on prefix sum, and ...
122 views

### 2D discrete motion planner

I am writing a 2D discrete motion planner for a task with specific instructions. The instructions for the search algorithm are contained entirely in the docstring for the ...
77 views

### Leet Code :: Merge Binary Tree :: Time Complexity [closed]

Problem Statement: Given two binary trees and imagine that when you put one of them to cover the other, some nodes of the two trees are overlapped while the others are not. You need to merge them into ...
1k views

### Sort multidimensional array based of the difference in the value

Sort multidimensional array based of the difference in the value, if value is same sort on first column. Constrains: No of rows can be any but fixed no of column ie 2. Example: <...
134 views

### Binary search for IOI problem: Cave

Question http://www.ioinformatics.org/locations/ioi13/contest/day2/cave/cave.pdf Code ...
1k views

### Find the length of minimum sub array with maximum degree in an array

I tried solving a problem in Hackerrank which is to find the length of minimum sub array with maximum degree in an array. For example, consider the example {2, 2, 1, 2, 3, 1, 1} the min sub-array ...
111 views

### Comparing two n×m matrices

I have to do a pairwise compare of a couple of text files. They have the following format: ...
48 views

### RTB, SSPs is True 2nd Price Auction Program

I've created this program that is intended to check if SSPs in RTB auctions run true second price auction. The program is running properly and returning the values as desired. I would like to get ...
932 views

### Most popular element with count in Array with Java

Here is the input array of int values Example: { 5, 4, 6, 5, 1, 0, 7, 7, 3, 5 } Find the most repeated element with its count, example output; ...
242 views

### Find all pairs in an array whose absolute difference equals x

I have an array A of integers with n values and an integer x. I need to find all the pairs in that array whose absolute ...
106 views

### Adding input strings and finding occurrences of certain prefixes

A user inputs data using a keyword add word and when he wants to find words with particular prefix then he enters find keyword. ...
306 views

### Design a O(1) data structure

How would I implement a data structure that supports the following in constant time? I got this question at a job interview, and the following is my solution. Please check my approach, or suggest a ...
417 views

### N queens variation recursion Python 3

I am trying to solve a modified version of the N-queens problem, where the addition is that for any NxN board (3<=N<=12) there are M holes (0<=M<=N^2) that are placed at random (but given) ...
61 views

### Given an array of integers, find and print its number of negative subarrays on a new line

Given an array of N integers, find and print its number of negative subarrays (i.e sub arrays having negative summation) on a new line. My code is taking $\mathcal{O}(n^2)$ time. How can I improve ...
498 views

### Adding Combinations of Numbers in an Array

Could someone help me optimize this code for time complexity? What is the best way to do this that doesn't include nested for loops? Take an array of integers and return a list of sums of every ...
983 views

### Python PEMDAS calculator [closed]

The goal of this calculator is to evaluate an expression with PEMDAS in mind (no parenthesis yet, adding soon). Although the program works, I want to make it as efficient as possible with the approach ...
1k views

### Maximum consecutive subarray sum for a variable sliding window size

The Problem: Given an array of integers L find the largest sum of a consecutive subarray of size k or less. Constraints: ...
3k views

### Sort a stack of numbers in ascending order only using push

I have a stack of numbers ranging from 1 to 1 million representing a pile of numbered DVDs. Given the stack in random order I am to sort the stack by only taking an element from the stack and push it ...
2k views

### Counting the number of ways to break an amount into coins

I have an algorithm here that counts the number of ways that n cents can be represented using the following denominations: quarter: 25 cents dime: 10 cents nickel: 5 cents pennies: 1 cent There are ...
210 views

### Category of sorting algorithm and complexity [closed]

Just for fun, I wrote a sorting algorithm. I did not compare this with existing sorting algorithms.Can someone tell me what class of sorting algorithm this is and it's complexity? The algorithm ...
3k views

### Calculating the most profit from an array of stock prices

I'm a newbie learning how to code, and I am trying to find the most efficient way to calculate the most profit from an array of stock prices. For a given array,I have a list of stock prices over n ...
2k views

### Implementation of Prim's Algorithm to find minimum spanning tree

What is the time complexity of the following code? I'm implementing Prim's Algorithm with adjacency matrix representation of the graph and priority queue. ...
57 views

### Two approaches to count occurrences of one char in a String in Java

I have two approaches: First Approach: ...
954 views

### MaxCounters solution

I am doing this Codility problem You are given N counters, initially set to 0, and you have two possible operations on them: increase(X) − counter X is increased by 1, max counter − all ...
1k views

### Non-recursive implementation of MergeSort

I've been trying to internalize some of the basic sorting algorithms recently, and to do so I've been looking at their wikipedia pages to refresh myself with how they work, and then coding my own "...
2k views

### Finding the distance from each array element to the nearest zero entry

I wrote a program, that gets a certain array and replaces each value in the array with the distance from it to the closest zero value. Time complexity is $4n$ => $O(n)$. (please correct me if I'm ...
5k views

### Fish Food Chain of complexity O(N)

I understand that if you don't know the trick, it's not easy create a solution with a complexity of $O(N)$. However, I would like to ask you how to solve this tricky question: You are given two ...
1k views

### Find element that has been removed from a shuffled array

For a function to determine which element has been removed from a shuffled array, I came up with: ...
5k views

### HackerRank: Left Array Rotation in Python

Here is the problem on HackerRank. I want to know how I can improve this code. I am mainly trying to improve the following skills: Documentation, functional programming (top-down approach), accurately ...
857 views

### What are the time and space complexity of this algorithm? [closed]

What is the time and space complexity of this algorithm and can it be improved (how)? It generates random 4 digit even number and the adjacent 2 digits must be different. ...
83 views

### Make each element equal to its neighbouring element which is maximum in a matrix

I have a matrix and I want to make each of its element equal to the maximum of its neighbouring element and each time I increase number of counts till all the elements in the matrix becomes equal to ...
121 views

### Merge sort C# time and space efficiency

Please comment on time and space efficiency. ...
341 views

### Test whether two strings are anagrams of each other

What is the time/space complexity of this algorithm which checks if two strings are anagrams? My guess is that time is $O(n)$ and space $O(1)$ but I am not sure. Can it be improved? ...
298 views

### Find lexicographical permutations

I have tried many possible methods here but I am still not able to reduce the time complexity of below algorithm. The basic layout of my problem is as follows: I have a string that is composed of ...
3k views

### Removing duplicates from unsorted LinkedList

Removing Duplicates: ...
855 views

### Checking if a LinkedList is a palindrome

I would like to know if my code is $O(n)$ space complexity. The code checks if a doubly linked list is Palindrome. ...
1k views

### Find the total number of ways W, in which a sum S can be reached in N throws of a dice

I was solving this question: Given there is a 6 sided dice. Find the total number of ways W, in which a sum S can be reached in N throws. Example: S = 1, N = 6 => W = 0 S = 6, N = 6 => W ...
45 views

### Complexity for two approaches of finding next biggest palindrome of a number

I have come up with a problem online about the next biggest palindrome of a number and i have solved the problem by two different approaches in python. The first one is, ...
3k views

### Print Z pattern from 2D String array

I am trying to print the Z pattern, but the time complexity is coming to $O(n^2)$. Is there any way to reduce the time complexity? ...
73 views

### Dividing a ThreadPool class into component classes to reduce/isolate complexity

I have a ThreadPool class which has grown to a point where it is becoming difficult to keep all of this unit of work in mind. It is also becoming harder to read. ...
6k views

### Sort a given string in ascending order

This code sort the string below in ascending order. I'd prefer it split-up in two or three smaller, simpler methods. I'm also wondering whether my algorithm has a decent time complexity. Given ...
263 views

### Checking whether one string is a permutation of another

I solved the standard "write a method to determine if one string is a permutation of the other" question with the following code, using xor, ...
2k views

### Finding the maximum distance from the starting node

I've tried everything to make my program faster but with 250 nodes my code takes around 9 seconds to print the result, and with 5000 nodes it took around 260 seconds. Is there a way to make my ...