# 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.

369 questions
Filter by
Sorted by
Tagged with
21k views

### Searching in an array in less than O(n) time

I have an array where each element is either one less or one greater than the preceding element $\{x_i = x_{i-1} \pm 1\}$. I wish to find an element in it in less than $O(n)$ time. I've ...
4k views

### The fastest way to find one unique value when all other values are the same

I have completed this question and I am wondering what is the fastest way to solve it. The question is "There is an array with some numbers. All numbers are equal except for one. Try to find it!&...
30k views

### Find all paths from source to destination

Given a directed connected graphs, find all paths from source to destination. Looking for code review, optimizations and best practices. Also need help figuring out complexity, which in my best ...
799 views

### 'Team Split' problem

Below is my solution for this 'Team Split' problem. In summary, the problem is to find relative strength of 2 teams by finding the difference between their total strength (individual strengths can be ...
1k views

### Finding the most popular element with C# given O(1) space complexity requirement

I have tried to solve the following problem in C# with LINQ: Given an integer array, find the most frequent number and it's count in the array. If multiple numbers have the same highest frequency ...
8k views

### “Algorithmic Crush” problem hitting timeout errors

This is the HackerRank problem Algorithmic Crush: You are given a list of size N, initialized with zeroes. You have to perform ...
4k views

### Check if one string is a permutation of another using Python

The code below is an attempt at a solution to an exercise from the book "Cracking the Coding Interview." I believe that the worst case time complexity of the code below is $O(n)$, where n is the ...
2k views

### Nonogram puzzle solution space

I've written some code to brute-force enumerate the solution space of nonogram puzzles up to a certain size. It does a good job up to the first ~4 billion puzzles, but I run out of disk space to store ...
1k views

### Given some integers, return the k most frequent elements

Given a non-empty array of integers, return the k most frequent elements. For example, given [1,1,1,2,2,3] and k = 2, return <...
587 views

### Seating Students (partitioning sort of)

The goal of this code is to seat students in a classroom based on a single test score. We want students to be evenly distributed across the class such that every student is positioned next to the ...
1k views

### Extended stable marriage challenge

I've written a solution for the stable marriage problem in the case that the number of men is not equal to the number of women. My problem is not that I can't prove my code is right. The problem is I ...
1k views

### Refactoring my problem-solution to reduce complexity

I need some help refactoring my solution to the problem below: Problem Statement An Association of Computer Scientists meets on a weekly basis. There is a certain number of seats in the meeting room ...
2k views

### Are the sum of two numbers desired?

Given two input arrays [-1, 8, 3] and [3, 7, 2] your function will return true if any two of the numbers in the first array add ...
1k views

### Finding Pythagorean triplet in array

We have an integer array as: private int[] arr = {1, 3, 5, 14, 18, 29, 78}; We have a function which takes three inputs of the array and checks whether: ...
16k views

### Checking if three numbers sum to a given number

I'm working on the following interview practice problem, and got the following solution, which runs in worst case n! time (best case constant), and I'm trying to ...
12k views

### Calculate square of a number without multiplication

I wrote these two methods to calculate the square of a number: ...
3k views

### Getting filtered autolist

Is there a better way to write the following code fragment? I can't have more than 10 conditional statement in my method as it gives cyclomatic complexity. ...
15k views

### Finding overlapping time intervals

You have two lists with meetings scheduling (start time, end time). Meetings in single list don't intersect. Find all intersecting meetings across the two lists. Is my complexity $O(N M)$? If I use ...
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 ...
568 views

### Minimum sub-array challenge

Below is my solution to finding the minimum product sub-interval. It passed 8/12 or so test cases, but the other test cases timed out if they hadn't finished within 2 seconds. When I compile this code ...
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: ...
427 views

### Min sub array size with a given sum

How can the time complexity of the following code be improved (assuming it's $O(N^2)$)? What about style and patterns? This code is trying to find the minimum subarray size that adds up to given sum ...
6k views

### URLify a string using Python

I have been working my way through the exercises in the book Cracking the Coding Interview. I wanted to get feedback for the following exercise. Write a method to replace all spaces in a string ...
1k views

### Codility MaxCounters peformance in Python capping out at 77% performance

My problem is quite similar to the question found here, except I am attempting to answer the question in Python. Given an array of N counters, all initialized to 0, and an array ...
1k views

### Find the smallest positive integer that is absent from a given array

I made the acquaintance of big-O a couple of weeks ago and am trying to get to grips with it, but although there's a lot of material out there about calculating time complexity, I can't seem to find ...
2k views

### Solving 'decent numbers' that follow specific division rules

HackerRank Problem Statement I have to find the largest 'decent number' having N digits. A decent number has the following properties: 3, 5, or both as its digits....
856 views

### Regular Expression Evaluator

Task to be accomplished: Write a function that takes two strings s and p as arguments and returns a boolean denoting whether s matches p. p is a sequence of any number of the following: a-z - ...
353 views

### Calculating the mean differences of subarrays

I'm trying to devise a way to calculate the mean differences (the absolute average differences between any two values in a set), of sub-arrays (starting from arbitrary indices) in an ...
170 views

### An array with $O(\log\ n)$ time complexity for all operations

Does this exist already? It's an array (=variable-size list with integer indices) where add/remove/set and get all take $O(\log\ n)$ time. I couldn't find this anywhere, so I made up the name "Log-...
1k views

### Finding largest subset of line segments that don't intersect

I completed a challenge of codeeval called BayBridges. It can be found here. I have uploaded my code on GitHub here. In summary, the challenge is to take a list of line segments, each specified by ...
12k views

### Rotate Matrix using Python

This is my solution to Exercise 1.7 from Cracking the Coding Interview. I would appreciate any feedback on coding style and algorithm efficiency. I do know that there is an existing function in ...
4k views

### Finding the count of negative sub-arrays for a given array

I want to improve my implementation for the following problem: You are given an array of n integers. A sub-array is "Negative" if sum of all the integers in that ...
778 views

### Longest 'balanced' substring

I was given a task where given a string of '0's and '1's, return the longest substring where the count of '0's and '1's are equal. I was told also that the code should be O(n) and space O(1). Below ...
100 views

### Joining collections… because it's fun

I'm working on a LinqEnumerable class (reviewable here), and I'm no Big-O expert and I'm pretty bad with algorithms, so I wonder what the complexity is for what I'...
9k views

### Finding the largest repeating substring

Here's my code that takes a large string, and searches for the longest reoccurring substring. It compares the first letter with every other until it finds a match, then saves it. Then it compares the ...
183 views

### Compute the height of a tower made of buckets

I need to speed up my algorithm. It is about finding the height of a tower. The tower is built from buckets. Each bucket has height and radius (1 <= height,radius <= 1000). Variable ...
2k views

### Codility “max slice swap” challenge

Problem Description: Find the maximum sum of a compact subsequence of array elements after performing a single swap operation. Solution: ...
13k views

### Finding the most common character in a string with a hash map

I created a method for finding the most common character in a string (using HashMap): ...
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 ...
12k views

### Find maximum difference between values in an array

My task is to use the following pseudocode and improve it (make it run faster). Also I have to analyze the runtime of the given pseudocode and of my new code that i improved. What does this algorithm ...
2k views

### Finding unique triplets adding up to 0

I am working on a problem "3Sum", in which, given an array S of n integers, are there elements ...
1k views

### Google's Python exercise about lists very different from the given solution

I found some Python exercises that were made by Google in their Python classes and decided to spend some time with them. Given the following description: E. Given two lists sorted in increasing order,...
2k views

### Sum the exponents of the prime factors of a number

My goal is to find the sum of the exponents of the prime factors of an integer. I wrote the code below with the complexities specified here (I am not 100% sure of the complexities though): Runtime ...
5k views

### Algorithm to compute the n-th derivative of a polynomial in Python

As a personal exercise, I'm trying to write an algorithm to compute the n-th derivative of an ordered, simplified polynomial (i.e., all like terms have been combined). The polynomial is passed as an ...
2k views

### Simplify function to sum the absolute value of the difference between all pairs of elements of a sorted array

Given a sorted array of N elements, I need to find the absolute sum of the differences of all elements. Given 4 elements (1, 2, 3 and 4): |1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10 Here is my code ...
854 views

### Finding the shortest excerpt that contains all search terms

Write a function called answer(document, searchTerms) which returns the shortest snippet of the document, containing all of the given search terms. The search ...
3k views

### A partition algorithm for positive integers

I have encountered the following problem that I found very interesting to solve: Given an array of positive integers {a1, a2, ..., an} you are required to partition the array into 3 blocks/...