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.

Filter by
Sorted by
Tagged with
12
votes
3answers
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 <...
1
vote
1answer
57 views

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

I have two approaches: First Approach: ...
3
votes
2answers
898 views

Find all occurrences of all permutations of a shorter string within a longer string

Input is two strings, the first string being the long string and the second smaller string being the permuted string. The output should return the starting indices of all occurrences as well as the ...
5
votes
2answers
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 "...
-4
votes
1answer
856 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. ...
4
votes
1answer
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 ...
1
vote
1answer
121 views

Merge sort C# time and space efficiency

Please comment on time and space efficiency. ...
0
votes
1answer
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? ...
4
votes
2answers
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 ...
3
votes
2answers
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. ...
7
votes
3answers
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 ...
1
vote
2answers
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? ...
3
votes
1answer
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, ...
5
votes
1answer
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 ...
4
votes
2answers
262 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, ...
5
votes
2answers
968 views

JavaScript function for finding perfect numbers

The following function has been created for finding "Perfect Numbers". About Perfect Numbers: Wikipedia ...
2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
76 views

One-off string detection

Problem spec from CareerCup. Given two strings, return boolean True/False if they are only one edit apart. Edit can be insert/delete/update of only one character in the string. Eg. True xyz,xz xyz,...
2
votes
2answers
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 ...
7
votes
1answer
180 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 ...
7
votes
1answer
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 ...
12
votes
1answer
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 ...
4
votes
2answers
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 ...
4
votes
4answers
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: ...
5
votes
1answer
949 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 ...
1
vote
1answer
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 ...
4
votes
1answer
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 [...
2
votes
1answer
563 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 ...
13
votes
7answers
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 ...
3
votes
1answer
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. ...
3
votes
1answer
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'...
2
votes
0answers
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 (...
1
vote
2answers
230 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, ...
5
votes
2answers
238 views

Finding substrings within arrays

I need to find the substrings within my array. If I have an array: ["abc", "abcd", "abcde", "xyz"], my method should return the array members: ...
-1
votes
1answer
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 ...
2
votes
1answer
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 - ...
5
votes
2answers
6k views

Find the number of K-Complementary pairs in an array

Below is the program to find k-complementary pairs: K = A[i] + A[j];. ...
3
votes
1answer
965 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 ...
0
votes
1answer
860 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: ...
2
votes
1answer
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
2answers
2k views

'Zero out' a matrix using Python

Below is my code for an attempted solution to cracking the coding interview exercise 1.8 written in python 3.5. The problem statement is: Write an algorithm such that if an element in an MxN ...
7
votes
1answer
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 ...
2
votes
2answers
8k views

Simple string compression in Python

This is my solution to exercise 1.6 in Cracking the Coding Interview. I am interested in receiving feedback on the coding style and time/space complexity. The exercise statement is: Implement a ...
4
votes
2answers
3k views

Check if two strings are one 'edit' apart using Python

The code below is my solution in python 3 to exercise 1.5 in Cracking the Coding Interview. I would appreciate feedback on both the algorithm (improvements to space and time complexity) and/or coding ...
4
votes
2answers
4k views

Check if a string is a permutation of a palindrome using Python

This is a solution to exercise 1.4 from Cracking the Coding Interview written using Python 3. Given a string, write a function to check if it is a permutation of a palindrome. Example: 'Tact Coa' ...
3
votes
3answers
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 ...
9
votes
3answers
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 ...