# 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
4answers
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 ...
1answer
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. ...
1answer
11k views

### Counting all substrings with exactly k distinct characters

Problem Statement : Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that has exactly k distinct characters. Example: Input: abc, k = 2 Output: 2 ...
1answer
714 views

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

Created the following method: ...
1answer
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 ...
2answers
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 ...
3answers
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 ...
3answers
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: ...
2answers
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 ...
0answers
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 ...
1answer
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: ...
2answers
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 ...
1answer
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 ...
1answer
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 ...
2answers
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 ...
6answers
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 ...
2answers
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? ...
1answer
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) ?
1answer
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 ...
2answers
9k views

### JavaScript function to convert decimal number to binary

I was recently asked this in an interview for a front-end position and I came up with something like the code below, which seems to work but is clunky. (...
1answer
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 ...
0answers
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 ...
1answer
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 ...
1answer
1k views

### Find given number by summing up integers from 2 sorted arrays

I am working on an algorithm question in which I need to find out pair of number out of 2 sorted arrays which sum up to the given number. I need to print out the indexes of those pairs rather than ...
3answers
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 ...
1answer
1k views

### Finding the sum closest to a target number

Wallace the Weightlifting Walrus is training for a contest where it will have to lift 1000 kg. Wallace has some weight plates lying around, possibly of different weights, and its goal is to add some ...
2answers
6k views

### Sorting a Stack in ascending order

Here's my implementation of sorting a stack in ascending order. The problem statement is as follows : Write a program to sort a stack in ascending order (with biggest items on top). You may use ...
1answer
135 views

### Worst case runtime analysis of a string partitioning algorithm

Give all the partitionings of a string s such that every substring of the partition is a palindrome What is the time complexity of this solution? And, how can I improve my code overall? ...
0answers
58 views

### Byzantine payment processing code

I've been working on a large Ruby on Rails application for several years. We inherited it and refactored and upgraded it, but there are some sections that have not been touched in at least 5 years (...
2answers
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? ...
2answers
235 views

### Improving the time complexity of my back pack algorithm

Is there anyone who can help me improve the time complexity of this backpack algorithm, for which I already use sliding array to improve the space complexity. The problem is as follows: Given <...
3answers
395 views

### Simple 1-dimensional labyrinth

I am training a colleague who is familiar with Python but has a limited knowledge of C# and complexity. I thought the following problem could be a good start. You are in a desert, there is a (...
0answers
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 ...
3answers
225 views

### Long arithmetic addition in JS

The implementation of the algorithm which adds two number in string form with arithmetic rules. ...
1answer
75 views

### Finding all backedges in an undirected graph

I have tried to implement the DFS algorithm to find all the back-edges in a graph that lead to a cycle in the graph: ...
1answer
339 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. ...
1answer
510 views

### Printing a singly linked list with time complexity O(n) and space complexity O(sqrt(n)) [closed]

My aim is to write a method which prints contents of a singly linked list in reverse order with time complexity $O(n)$ and space complexity $O(\sqrt{n})$. The best I could come up with is to store ...
2answers
854 views

### Count number of matching nodes in a Binary tree

Problem Count the number of matching nodes in the subtree rooted at some node n. Solution ...
2answers
1k views

### Determining if two strings are anagrams

Two strings are said to be anagrams of each other if the letters of one string may be rearranged to make the other string. For example, the words 'elvis' and 'lives' are anagrams. In this ...
1answer
520 views

### Check if a Binary Tree is full

Problem statement Given a node check whether the sub-tree rooted at given node is full binary tree or not. Definition A full binary tree (sometimes proper binary tree or 2-tree) is a tree in ...
1answer
98 views

### Knights Tour — Something I am doing wrong

I have an assignment to write a knights tour backtracking program in Java where the professor says to: Eliminate backtracking time by: ...
1answer
307 views

### How to tweak Tape Equilibrium assignment on Codility to be of complexity O(N)?

Why Codility detects my solution for Tape Equilibrium to have complexity of $O(n^2)$. How can I make my code better? ...
1answer
662 views

### Monitoring the recursive growth of a zombie rabbit population

Breeding like rabbits Write a function answer(str_S) which, given the base-10 string representation of an integer $S$, returns the largest n such that \\$R(...
1answer
729 views

### SQL Permission Handling in WinForms

For my application, I've opted to use Integrated Security with Windows Authentication to access the SQL database. I've created AD security groups for each role and given them ...
3answers
844 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 ...
2answers
630 views

### Finding number of number pairs with given difference [closed]

pairs() is a function which returns the total number of combinations whose difference is k. ...
5answers
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): ...
1answer
74 views

### Summing sub arrays (maximal subarray)

I have this piece of code, and I want to make if the way I'm calculating the time complexity is valid: ...
2answers
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 ...
2answers
1k views

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

Disclaimer: Although I do believe that this is somewhat a code review, I'm not sure if this kind of question applies to the site; if not, please let me know and I'll delete it promptly. I found some ...