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

339 questions
Filter by
Sorted by
Tagged with
20k 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 ...
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 ...
786 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 ...
3k 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 ...
299 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 ...
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 <...
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 ...
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. ...
4k 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 ...
556 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: ...
417 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 ...
14k 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 ...
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 ...
297 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....
847 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 - ...
351 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 ...
157 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 ...
698 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 ...
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 ...
96 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'...
8k 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 ...
174 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: ...
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 ...
11k 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 ...
4k 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 ...
841 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 ...
2k 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/...
5k 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 ...
662 views

745 views

### Finding pairs of numbers within A that add up to N

I am working on an interview question from Amazon Software Interview: Given an integer N and an array of unsorted integers A find all pairs of numbers within A which add up to N I have a working ...
10k 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 ...
176 views

### Check consistency of a list of statements, with fuzzy rhyme matching

I made a program today that solves the following problem on a programming competition site (open.kattis.com): Check if all statements with the following format X is Y or X not Y are consistent. X and ...
204 views

### Extending the extended Stable Marriage Problem using a Python class

As soon as I saw this open source paper, I thought that the best way to replicate their code would be using a python class. After having replicated and extended the ...
11k 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): ...