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

### Parsing URL query strings in AngularJS

Here are two very small blocks of code I wrote while trying to fix a bug in AngularJS. Both do the same thing. I'm trying to understand how the two differ, mainly in terms of the tradeoff between cpu ...
97 views

### Random permutation with defined order of last occurrences

This Python function takes two arguments: chr_list which is a mutable sequence of characters c ...
88 views

### High execution time on number partitioning program in Python 2.7

I am writing a program to count only the partitions of a number with distinct parts. I am using a bottom-up approach to dynamic programming to generate partition lists from previously obtained ...
181 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 ...
2k views

### Check for valid parentheses nesting

I found this question on leetcode and that was my answer ... But someone told me it's too bad that it takes $O(n^3)$ I am not sure that it takes all that time ... and trying to find better ...
363 views

### Split DAG into disjoint sets

I wrote an algorithm to separate a DAG into disjoint sets of vertices. I was hoping to have some comments on algorithmic complexity and efficiency of the Python code. Notably, I don't like the adding ...
5k views

### Stable radix sort in-place using O(1) space

I am trying to implement a stable radix sort in place with O(1) space. I've seen Wikipedia, and I notice the C implementation is using a temporary variable to hold the sorted value for each pass, and ...
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 ...
168 views

### Does my Linklist implementation have memory leaks?

Are there any memory leaks in this linklist implementation.Also is the implementation correct?Can the time complexity be optimized? ...
61 views

### Finding the distance between every indices in an array that contain odd numbers

I'm doing this HackerRank problem which basically boils down to what I've written in the title. We have to find out the distance between all the odd values in the array. I've written this code below ...
889 views

### Lexicographically smallest wave like array without sorting

Given an array of integers, sort the array into a wave like array and return it. In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5..... Example: Given [...
565 views

### Taxicab numbers algorithm check

With the programming language skills that are available to me at the time, I've written this program to find the "taxicab numbers" (e.g. a number expressible as the sum of two cubes in two different ...
89 views

### SPOJ Aliens in a Train

I need to find the largest interval with a value less than a limit Lt. The data is as follows: For every test case T: Number of elements N, limit Lt N number of elements data I wrote the ...
2k views

### Finding line numbers of duplicate lines in a log file

I have a log file with a million lines, and my task is to code something that outputs the lines that have duplicates, and the line numbers. I've thought of two ways to approach this : 1) Use python'...
868 views

### Word Wrap via Dynamic Programming

Word Wrap problem in short: Given n words and a line length, break the words into lines in such a manner that minimizes the sum of the costs of all the lines. Consider the cost of each line being (...
231 views

### Massive file sorting algorithm

I was trying to sort a massive file of successive chars in C. I did some research and found a few file sorting algorithms that look the same. Their main idea is to read an amount of data to memory, ...
7k views

### Complexities: Filtering out nested array inside an array

I am doing some iteration over an array which have another set of array (the nested array). I need to .map() the outer array in such a way that it should filter out ...
2k views

### Find the longest subarray with sum less than K

The problem consist of finding the longest contiguous subarray with a sum less than a given integer K. The input data are: K - ...
968 views

### Calculating binary tree height as asked in the interview

Input: The first line contains the number of vertices $n$. The second line contains $n$ integer numbers from the range $\left[−1, n − 1\right]$ representing the $0$-based index of the ...
861 views

### Subset sum simple iterative implementation

Here is the simplest iterative implementation of Subset sum problem that I could come up with1, as a follow up to this recursive implementation of the same problem: ...
277 views

### Modified Z-Algorithm for string similarity with one char difference

I have modified a Z-Algorithm for string similarity in order to match strings which differ in 0 or 1 char. However, it seems much slower than original Z-Algorithm although from my point of view there ...
124 views

### Infinite Monkey Theorem Python Comparison

I wrote code to demonstrate the Infinite Monkey Theorem which states that if a monkey types at a keyboard for an infinite amount of time it will almost surely type a given text such as William ...
497 views

### Stack which finds the minimum element

Write a program to implement stack which implements min a method which gives the minimum element below the top element in the stack. ...
360 views

### URLIfy a character array using Python - follow-up

This is a follow up to my last code review: URLify a string using Python This problem has been reviewed in other languages, but I tried to solve this without looking at those answers. I am hoping ...
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 ...
46 views

### Creating List of String elements that occur a certain amount of times using only the List ADT

I am tasked with creating a list with no duplicates of all String elements, in this case first names, of an ArrayList. The method is passed a threshold, and the ...
714 views

### Finding a max element in an array in Java

Created the following method: ...
2k views

### Iterative solution for generating all permutations of a string

I know the runtime for generating all permutations is supposed to be $O(n!)$. I'm not sure if the code I wrote for it runs in $O(n!)$ though. I'm having trouble analyzing its runtime. The ...
221 views

### Function to check truth value of a specific statement

I want to check the truth of A + B - (A & B) == A | B for N-bit numbers. For example, here's a "truth" table for 2-bit numbers. (I know I'm taking liberty with ...
337 views

### Count Acute, Right and Obtuse triangles from n side lengths

Problem Statement: We have $N$ sticks. The size of the $i$th stick is $A_i$. We want to know the number of different types of triangles created with each side from a single different stick. ...
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: ...
244 views

### TopCoder problem “Substitute” - SRM 160 (Division II Level One)

I have solved the problem "Substitute" at Topcoder. A simple, easy to remember system for encoding integer amounts can be very useful. For example, dealers at flea markets put the information about ...
215 views

### Improving time efficiency of finding maximum area rectangles in a histogram

Here's my solution but I am looking for ways to improve the time complexity of solution. Also this question is categorized as being solved by stack so I would like to know how to approach it using ...
418 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 ...
2k views

### Faster palindrome checker in Java

I wonder if there could be a faster palindrome checker in Java. The best one I have is O(n/2) which is O(n) eventually: ...
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 ...
87 views

### Given a set of random strings, write a function that returns a set that groups all the anagrams together in objective-c

I would like to get feedback on the solution and a question regarding Big O. I am first converting each character in the string into the array and that would be O(n) then i am sorting the array O(n ...
12k views

### Calculate square of a number without multiplication

I wrote these two methods to calculate the square of a number: ...
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 ...
143 views

### Summing all keys in the leaves of a tree

My program takes 35 sec to run example 2. How can I make my program faster? ...
13k views

### Permutations of any given numbers

I have solved one programming problem where we have to find all the permutations of given numbers. For example, $[1,2,3]$ have the following permutations: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,...
109 views

### Reverse a string [closed]

I use this for reversing a string, but it has O(n) : reverse(y.begin(),y.end()); How can I reverse a string in O(n/2) ?
13k views

...
211 views

### Local variable lookup table

I'm currently in the process of writing my own programming language and the Virtual Machine for the language is responsible for handing all of the local variable scopes. I need to support the ...
56 views

### Return Object[] while connecting to DB once

I have written this code according to my requirements. But after finishing the code, it looks like there are too many loops. I have reduced it as much as I can. Can you find any improvements that I ...
143 views

### ACM-ICPC HackerRank challenge in C++

I was doing a programming question in C++ at HackerRank. Given a set of up to 500 bitstrings, each up to 500 bits long, the task is to find the pair a and b such that the bitwise OR contains the most ...
79 views

### Sum to zero of all triples in a list - n^2 running time

As part of an interview, I had to submit a code sample to solve the classical "triples sum to 0" problem. The reviewer said the algorithm needed to be in n2 time, and I was later informed that the ...